Рубрики

Расческа сортировка

Comb Sort — это в основном улучшение по сравнению с Bubble Sort. Пузырьковая сортировка всегда сравнивает соседние значения. Таким образом, все инверсии удаляются по одному. Comb Sort улучшает Bubble Sort, используя разрыв размером больше 1. Разрыв начинается с большого значения и уменьшается в 1,3 раза на каждой итерации, пока не достигнет значения 1. Таким образом, Comb Sort удаляет более одного подсчета инверсии с одним своп и работает лучше, чем Bubble Sort.

Эмпирически было установлено, что коэффициент сжатия равен 1,3 (при тестировании Combsort в более чем 200 000 случайных списках) [Источник: Wiki ]

Хотя в среднем он работает лучше, чем Bubble Sort, в худшем случае остается O (n 2 ).

Ниже приведена реализация.

C ++

// C ++ реализация Comb Sort
#include<bits/stdc++.h>

using namespace std;

  
// Найти разрыв между элементами

int getNextGap(int gap)

{

    // Уменьшить разрыв по коэффициенту сжатия

    gap = (gap*10)/13;

  

    if (gap < 1)

        return 1;

    return gap;

}

  
// Функция для сортировки [0..n-1] с использованием Comb Sort

void combSort(int a[], int n)

{

    // Инициализируем пробел

    int gap = n;

  

    // Инициализировать swapped как true, чтобы убедиться, что

    // цикл запускается

    bool swapped = true;

  

    // Продолжаем работать, пока разрыв больше 1 и последний

    // итерация вызвала своп

    while (gap != 1 || swapped == true)

    {

        // Найти следующий пробел

        gap = getNextGap(gap);

  

        // Инициализируем поменять местами как ложь, чтобы мы могли

        // проверяем, произошел ли обмен

        swapped = false;

  

        // Сравнить все элементы с текущим разрывом

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

        {

            if (a[i] > a[i+gap])

            {

                swap(a[i], a[i+gap]);

                swapped = true;

            }

        }

    }

}

  
// Драйвер программы

int main()

{

    int a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};

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

  

    combSort(a, n);

  

    printf("Sorted array: \n");

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

        printf("%d ", a[i]);

  

    return 0;

}

Джава

// Java-программа для реализации Comb Sort

class CombSort

{

    // Найти разрыв между элементами

    int getNextGap(int gap)

    {

        // Уменьшить разрыв по коэффициенту сжатия

        gap = (gap*10)/13;

        if (gap < 1)

            return 1;

        return gap;

    }

  

    // Функция для сортировки arr [] с использованием Comb Sort

    void sort(int arr[])

    {

        int n = arr.length;

  

        // инициализируем пробел

        int gap = n;

  

        // Инициализировать swapped как true, чтобы убедиться, что

        // цикл запускается

        boolean swapped = true;

  

        // Продолжаем работать, пока разрыв больше 1 и последний

        // итерация вызвала своп

        while (gap != 1 || swapped == true)

        {

            // Найти следующий пробел

            gap = getNextGap(gap);

  

            // Инициализируем поменять местами как ложь, чтобы мы могли

            // проверяем, произошел ли обмен

            swapped = false;

  

            // Сравнить все элементы с текущим разрывом

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

            {

                if (arr[i] > arr[i+gap])

                {

                    // Поменять местами arr [i] и arr [i + gap]

                    int temp = arr[i];

                    arr[i] = arr[i+gap];

                    arr[i+gap] = temp;

  

                    // Установить подкачку

                    swapped = true;

                }

            }

        }

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        CombSort ob = new CombSort();

        int arr[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};

        ob.sort(arr);

  

        System.out.println("sorted array");

        for (int i=0; i<arr.length; ++i)

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

  

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Python программа для реализации CombSort

  
# Найти следующий пробел из текущего

def getNextGap(gap):

  

    # Сокращение разрыва по коэффициенту усадки

    gap = (gap * 10)/13

    if gap < 1:

        return 1

    return gap

  
# Функция для сортировки arr [] с использованием Comb Sort

def combSort(arr):

    n = len(arr)

  

    # Инициализировать пробел

    gap = n

  

    # Инициализируйте swapped как true, чтобы убедиться, что

    # цикл работает

    swapped = True

  

    # Продолжайте бегать, пока разрыв больше 1 и последний

    # итерация вызвала своп

    while gap !=1 or swapped == 1:

  

        # Найти следующий пробел

        gap = getNextGap(gap)

  

        # Инициализировать поменять местами как ложь, чтобы мы могли

        # проверить, произошел ли обмен

        swapped = False

  

        # Сравнить все элементы с текущим разрывом

        for i in range(0, n-gap):

            if arr[i] > arr[i + gap]:

                arr[i], arr[i + gap]=arr[i + gap], arr[i]

                swapped = True

  

  
# Код драйвера для проверки выше

arr = [ 8, 4, 1, 3, -44, 23, -6, 28, 0]

combSort(arr)

  

print ("Sorted array:")

for i in range(len(arr)):

    print (arr[i]),

  

  
# Этот код предоставлен Мохитом Кумрой

C #

// C # программа для реализации Comb Sort

using System;

  

class GFG

{

    // Найти разрыв между элементами

    static int getNextGap(int gap)

    {

        // Уменьшить разрыв по коэффициенту сжатия

        gap = (gap*10)/13;

        if (gap < 1)

            return 1;

        return gap;

    }

  

    // Функция для сортировки arr [] с использованием Comb Sort

    static void sort(int []arr)

    {

        int n = arr.Length;

  

        // инициализируем пробел

        int gap = n;

  

        // Инициализируем поменять местами как истину

        // убедитесь, что цикл работает

        bool swapped = true;

  

        // Продолжайте работать, пока разрыв больше

        // 1 и последняя итерация вызвала своп

        while (gap != 1 || swapped == true)

        {

            // Найти следующий пробел

            gap = getNextGap(gap);

  

            // Инициализируем поменять местами как ложь, чтобы мы могли

            // проверяем, произошел ли обмен

            swapped = false;

  

            // Сравнить все элементы с текущим разрывом

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

            {

                if (arr[i] > arr[i+gap])

                {

                    // Поменять местами arr [i] и arr [i + gap]

                    int temp = arr[i];

                    arr[i] = arr[i+gap];

                    arr[i+gap] = temp;

  

                    // Установить подкачку

                    swapped = true;

                }

            }

        }

    }

  

    // Метод драйвера

    public static void Main()

    {

        int []arr = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};

        sort(arr);

  

        Console.WriteLine("sorted array");

        for (int i=0; i<arr.Length; ++i)

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

  

    }

}

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

Выход :

Sorted array: 
-44 -6 0 1 3 4 8 23 28 56 

Иллюстрация:
Пусть элементы массива будут

8, 4, 1, 56, 3, -44, 23, -6, 28, 0

Первоначально значение разрыва = 10
После усадки значение разрыва => 10 / 1,3 = 7 ;

 8 4 1 56 3 -44 23 -6 28 0
-6 4 1 56 3 -44 23  8 28 0
-6 4 0 56 3 -44 23  8 28 1

Новое значение разрыва => 7 / 1,3 = 5 ;

-44 4 0 56 3 -6 23 8 28 1
-44 4 0 28 3 -6 23 8 56 1
-44 4 0 28 1 -6 23 8 56 3

Новое значение разрыва => 5 / 1,3 = 3 ;

-44 1  0 28 4 -6 23 8 56 3
-44 1 -6 28 4  0 23 8 56 3
-44 1 -6 23 4  0 28 8 56 3
-44 1 -6 23 4  0  3 8 56 28

Новое значение разрыва => 3 / 1,3 = 2 ;

-44 1 -6 0 4 23 3 8 56 28
-44 1 -6 0 3 23 4 8 56 28
-44 1 -6 0 3 8 4 23 56 28

Новое значение разрыва => 2 / 1,3 = 1 ;

-44 -6 1 0 3 8 4 23 56 28
-44 -6 0 1 3 8 4 23 56 28
-44 -6 0 1 3 4 8 23 56 28
-44 -6 0 1 3 4 8 23 28 56 

no more swaps required (Array sorted)

Сложность по времени: сложность этого алгоритма в наихудшем случае составляет O (n 2 ), а сложность в наилучшем случае — O (n).

Вспомогательное пространство: O (1).

Тест на расческу

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


Фотосъёмка:






Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz

Выбор сортировки , Bubble Сортировка , вставка Сортировка , Merge Сортировка , Heap Сортировка , QuickSort , Radix Сортировка , Counting Сортировка , Ковш Сортировка , ShellSort , Pigeonhole Сортировать

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

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

Расческа сортировка

0.00 (0%) 0 votes