Сколько сравнений использует коктейльная сортировка? - PullRequest
Новая
       38

Сколько сравнений использует коктейльная сортировка?

0 голосов
/ 27 сентября 2019

Название.Я смущен количеством сравнений для коктейля.Bubble sort использует n * (n-1) / 2 сравнения, сколько использует коктейльная сортировка?

1 Ответ

1 голос
/ 27 сентября 2019

Bubble sort использует n*(n-1)/2 сравнения

Нет, если вы правильно его реализовали!

Это псевдокод для стандартной Bubble sort: 

procedure bubbleSort(A : list of sortable items )
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap( A[i-1], A[i] )
                swapped = true
            end if
        end for
    until not swapped
end procedure

(Источник: Википедия )

Как видите, сортировка Bubble останавливается, когда он проходит через список / массив без замены элементов.Таким образом, число обменов равно (n - 1) * p, когда p - это количество проходов.p будет меньше или равно n и будет зависеть от того, как упорядочен входной массив.

Анализ сложности дает O(N^2) как сложность наихудшего и среднего случая и O(N) как лучшуюcase.

В той же статье в Википедии описана оптимизированная сортировка Bubble, которая выполняет сравнение не более (n-1)*(n-2)/2, с n-1 в качестве наилучшего случая.Это примерно в 2 раза больше по сравнению со стандартной сортировкой Bubble.

Сортировка Cocktail Shaker описывается как альтернатива оптимизации по сравнению с Bubble sort.Это также дает примерно 2-кратное улучшение по сравнению со стандартной сортировкой Bubble.

(Источник Википедия )

Обратите внимание, что невозможно дать точную формулудля числа сравнений для любых этих алгоритмов сортировки.В каждом случае количество сравнений зависит от фактического входного массива, а не только от количества элементов.Мы можем дать точные формулы только для лучших и худших случаев.

...