13.04.2021

Сортировка расчёской


Сортировка расчёской (англ. comb sort) — это довольно[уточнить] упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991 г. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком).

В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1. Основная идея сортировки расчёской в том, что этот промежуток может быть гораздо больше, чем единица (сортировка Шелла также основана на этой идее, но она является модификацией сортировки вставками, а не сортировки пузырьком).

Алгоритм

В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди. Первоначальный разрыв между сравниваемыми элементами лучше брать с учётом специальной величины, называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами максимально, то есть равно размеру массива минус один. Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае сравниваются соседние элементы как и в сортировке пузырьком, но такая итерация одна.

Оптимальное значение фактора уменьшения 1,247... = 1 1 − e − ϕ {displaystyle 1{,}247...={ frac {1}{1-e^{-phi }}}} , где e {displaystyle e} — основание натурального логарифма, а ϕ {displaystyle phi } — золотое сечение.

Реализация на языке Паскаль

  • Заполняю массив случайными числами.
  • Завожу цикл с условием «i < i + j», которое буквально означает «i отличается от i + j».
  • Обнуляю i для того, чтобы при новом пробеге по массиву индекс не вышел за его границы.
  • Завожу внутренний цикл с условием «i + j <= n», которое буквально значит «сумма индекса i и расстояния j между a[i] и другим сравниваемым элементом не больше, чем самый большой индекс массива».
  • Если a[i] > a[i + j], то меняю их местами.
  • Увеличиваю i.
  • Уменьшаю j.
  • const n = 5; var a: array [0..n] of integer; i, jr: integer; j: real; begin for i := 0 to n do a[i] := Random(12); j := n; jr := Round(j); while i < i + jr do begin i := 0; jr := Round(j); while i + j <= n do begin if a[i] > a[i + Round(j)] then begin a[i] := a[i] + a[i + jr]; a[i + jr] := a[i] - a[i + jr]; a[i] := a[i] - a[i + jr]; end; Inc(i); end; j := j / 1.247; end; for i := 0 to n do begin for jr := 0 to i - 1 do begin if a[jr] > a[jr + 1] then begin a[jr] := a[jr] + a[jr + 1]; a[jr + 1] := a[jr] - a[jr + 1]; a[jr] := a[jr] - a[jr + 1]; end; end; end; Writeln(a); end.

    Цикл прекратится лишь тогда, когда j станет равной 0, иначе говоря, когда i станет равным i + j.

    Реализация на C++

    void comb(std::vector<int> &data) // data — название вектора (передаём по ссылке, чтобы вызов comb(array) менял вектор array) { double factor = 1.2473309; // фактор уменьшения int step = data.size() - 1; // шаг сортировки //Последняя итерация цикла, когда step==1 эквивалентна одному проходу сортировки пузырьком while (step >= 1) { for (int i = 0; i + step < data.size(); i++) { if (data[i] > data[i + step]) { std::swap(data[i], data[i + step]); } } step /= factor; } }

    Реализация на Java

    public static <E extends Comparable<? super E>> void sort(E[] input) { int gap = input.length; boolean swapped = true; while (gap > 1 || swapped) { if (gap > 1) gap = (int) (gap / 1.247330950103979); int i = 0; swapped = false; while (i + gap < input.length) { if (input[i].compareTo(input[i + gap]) > 0) { E t = input[i]; input[i] = input[i + gap]; input[i + gap] = t; swapped = true; } i++; } } }

    Реализация на PHP

    function combsort($array) { $sizeArray = count($array); // Проходимся по всем элементам массива for ($i = 0; $i < $sizeArray; $i++) { // Сравниваем попарно. // Начинаем с первого и последнего элемента, затем постепенно уменьшаем // диапазон сравниваемых значеный. for ($j = 0; $j < $i + 1; $j++) { // Индекс правого элемента в текущей итерации сравнения $elementRight = ($sizeArray - 1) - ($i - $j); if ($array[$j] > $array[$elementRight]) { $buff = $array[$j]; $array[$j] = $array[$elementRight]; $array[$elementRight] = $buff; unset($buff); } } } return $array; }

    Реализация на Python

    def combsort(alist): alen = len(alist) gap = (alen * 10 // 13) if alen > 1 else 0 while gap: if 8 < gap < 11: ## variant "comb-11" gap = 11 swapped = False for i in range(alen - gap): if alist[i + gap] < alist[i]: alist[i], alist[i + gap] = alist[i + gap], alist[i] swapped = True gap = (gap * 10 // 13) or swapped

    Реализация на JavaScript

    function combSorting(array) { var interval = Math.floor(array.length / 1.3); while (interval > 0) { for(var i = 0; i + interval < array.length; i++) { if (array[i] > array[i + interval]) { var small = array[i + interval]; array[i + interval] = array[i]; array[i] = small; } } interval = Math.floor(interval / 1.3); } }





    Яндекс.Метрика