Рубрики

C ++ программа для сортировки по Stooge

Сортировка по Стогу — это алгоритм рекурсивной сортировки. Это определяется как показано ниже (для сортировки по возрастанию).

Step 1 : If value at index 0 is greater than
         value at last index, swap them.
Step 2:  Recursively,
       a) Stooge sort the initial 2/3rd of the array.
       b) Stooge sort the last 2/3rd of the array.
       c) Stooge sort the initial 2/3rd again to confirm.

C ++

// C ++ код для реализации сортировки марионеток
#include <iostream>

using namespace std;

 
// Функция для реализации сортировки марионеток

void stoogesort(int arr[],int l, int h)

{

    if (l >= h)

      return;

 

    // Если первый элемент меньше последнего,

    // меняем их местами

    if (arr[l] > arr[h])

       swap(arr[l], arr[h]);

 

    // Если есть более 2 элементов

    // массив

    if(h-l+1>2)

    {

        int t = (h-l+1)/3;

 

        // Рекурсивная сортировка первых 2/3 элементов

        stoogesort(arr, l, h-t);

 

        // Рекурсивная сортировка последних 2/3 элементов

        stoogesort(arr, l+t, h);

 

        // Рекурсивная сортировка первых 2/3 элементов

        // еще раз для подтверждения

        stoogesort(arr, l, h-t);

    }

}
 
// Код драйвера

int main()

{

    int arr[] = {2, 4, 5, 3, 1};

    int n = sizeof(arr)/sizeof(arr[0]);

 

    // Вызов функции сортировки Stooge для сортировки

    // массив

    stoogesort(arr, 0, n-1);

 

    // Показать отсортированный массив

    for (int i=0; i<n; i++)

        cout << arr[i] << " ";

 

    return 0;

}

Выход:

1 2 3 4 5 

Пожалуйста, обратитесь к полной статье о Сортировке Stooge для более подробной информации!

Рекомендуемые посты:

C ++ программа для сортировки по Stooge

0.00 (0%) 0 votes