Рубрики

Java программа для сортировки гребней

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

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

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

// 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, чтобы мы могли

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

            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] + " ");

    }

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

Выход:

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

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

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

Java программа для сортировки гребней

0.00 (0%) 0 votes