Рубрики

Суррогатная сортировка

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

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.

ПРИМЕЧАНИЕ. Всегда выбирайте предел ((2/3) * N) для выбора элементов.


Иллюстрация:

Input :   2 4 5 3 1
Output : 1 2 3 4 5
Explanation:
Initially, swap 2 and 1 following above step 1.
          1 4 5 3 2
          Now, recursively sort initial 2/3rd of the elements.
          1 4 5 3 2
          1 3 4 5 2 
          Then, recursively sort last 2/3rd of the elements.
          1 3 4 5 2
          1 2 3 4 5
          Again, sort the initial 2/3rd of the elements to confirm final data is sorted.
          1 2 3 4 5

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;

}

Джава

// Java-программа для реализации сортировки марионеток

import java.io.*;

  

public class stooge {

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

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

    {

        if (l >= h)

            return;

  

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

        // чем последний, поменять их местами

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

            int t = arr[l];

            arr[l] = arr[h];

            arr[h] = t;

        }

  

        // Если есть более 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);

        }

    }

  

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

    public static void main(String args[])

    {

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

        int n = arr.length;

  

        stoogesort(arr, 0, n - 1);

  

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

            System.out.print(arr[i] + " ");

    }

}
// Код предоставлен Mohit Gupta_OMG <(0_o)>

python3

# Python-программа для реализации сортировки марионеток

  

def stoogesort(arr, l, h):

    if l >= h:

        return

   

    # Если первый элемент меньше

    # чем в прошлом, поменяйте их местами

    if arr[l]>arr[h]:

        t = arr[l]

        arr[l] = arr[h]

        arr[h] = t

   

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

    # массив

    if h-l + 1 > 2:

        t = (int)((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))

   

  
# производный

arr = [2, 4, 5, 3, 1]

n = len(arr)

  

stoogesort(arr, 0, n-1)

   

for i in range(0, n):

    print(arr[i], end = ' ')

  
# Код предоставлен Mohit Gupta_OMG <(0_o)>

C #

// C # программа для реализации сортировки марионеток

using System;

  

class GFG {

      

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

    static void stoogesort(int[] arr,

                            int l, int h)

    {

        if (l >= h)

            return;

  

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

        // чем последний, поменять их местами

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

            int t = arr[l];

            arr[l] = arr[h];

            arr[h] = t;

        }

  

        // Если их больше 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);

        }

    }

  

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

    public static void Main()

    {

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

        int n = arr.Length;

  

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

        // отсортировать массив

        stoogesort(arr, 0, n - 1);

  

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

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

            Console.Write(arr[i] + " ");

    }

}

  
// Этот код предоставлен Sam007.

Выход:

1 2 3 4 5 

Сложность времени выполнения сортировки марионеток может быть записана как,

T (n) = 3T (3n / 2) +? (1)

Решение вышеупомянутого повторения O (n (log3 / log1.5) ) = O (n 2.709 ), следовательно, оно медленнее, чем даже пузырьковая сортировка (n ^ 2).

Ссылка:
Википедия

Эта статья предоставлена DANISH KALEEM . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Суррогатная сортировка

0.00 (0%) 0 votes