Сортировка расчёской (Vkjmnjkftg jgvc~vtkw)

Сортировка расчёской
Визуализация сортировки расчёской
Предназначение	Алгоритм сортировки
Худшее время	$O(n^{2})$
Лучшее время	$O(n\log n)$
Среднее время	$\Omega (n^{2}/2^{p})$
Затраты памяти	$O(1)$
Медиафайлы на Викискладе

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

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

Алгоритм

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

Реализация

Ассемблерная вставка для x86-64 на Си

Для корректной работы следующей функции сортируемый массив должен быть глобальным.

const int N = 100;
int a[N];
double factor = 1.25;
void sort()
{
    asm(
    // variables
    "movsd factor(%rip), %xmm1\n"   // factor in xmm1
    "xorl %r9d, %r9d\n"             // counter j in the inside cycle in r9d
    "movl N(%rip), %r10d\n"         // n in r10d
    "leaq a(%rip), %r12\n"          // a in r12

    // making step
    "cvtsi2sdl %r10d, %xmm0\n"
    "divsd %xmm1, %xmm0\n"
    "cvttsd2sil %xmm0, %r8d\n"      // step in r8d

    "jmp Check_step\n"

    "Increment_j:"
    "incl %r9d\n"

    "Check_j:"
    "movl %r9d, %r11d\n"
    "addl %r8d, %r11d\n"
    "cmpl %r10d, %r11d\n"
    "jge Change_step\n"

    "movl (%r12, %r9, 4), %r13d\n"  // a[j]
    "movl %r9d, %r11d\n"            // new index in r11d
    "addl %r8d, %r11d\n"            // new index = j + step
    "movl (%r12, %r11, 4), %r14d\n" // a[j + 1]
    "cmpl %r14d, %r13d\n"
    "jle Increment_j\n"

    "movl %r13d, (%r12, %r11, 4)\n"
    "movl %r14d, (%r12, %r9, 4)\n"
    "jmp Increment_j\n"

    "Change_step:"
    "cvtsi2sdl %r8d, %xmm0\n"
    "divsd %xmm1, %xmm0\n"
    "cvttsd2sil %xmm0, %r8d\n"

    "Check_step:"
    "cmpl $1, %r8d\n"
    "jl Off\n"
    "xorl %r9d, %r9d\n"
    "jmp Check_j\n"

    "Off:"
    );
}

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

procedure CombSort(var v: array of Integer);
var
  i, gap, t: Integer;
  IsSorted: Boolean;
begin
  gap:=High(v); IsSorted:=False;
  while not IsSorted do begin
    gap:=Trunc(gap/1.25);
    if gap<=1 then begin
      gap:=1; IsSorted:=True;
    end;
    for i:=0 to High(v)-gap do
      if v[i]>v[i+gap] then begin
        t:=v[i]; v[i]:=v[i+gap]; v[i+gap]:=t;
        IsSorted:=False;
      end;
  end;
end;

var
  a: array [0..19] of Integer;
  i: Integer;
begin
  for i:=Low(a) to High(a) do a[i]:=High(a)-i;
  CombSort(a);
  for i:=Low(a) to High(a) do Write(' ',a[i]); WriteLn;
end.

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

using namespace std;
void combSort(int data[], int n) {
    int step = n;
    bool flag = false;
    while (step > 1 or flag) {
        if (step > 1) {
            step = step * 4 / 5;
        }
        flag = false;
        int i = 0;
        while (i + step < n) {
            if (data[i] > data[i + step]){
                flag = true;
                swap(data[i], data[i + step]);
            }
            i += step;
        }
    }
}

Реализация на 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.25);

        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 comb_sort(ls):
    n = len(ls)
    step = n
    flag = False
    while step > 1 or flag:
       if step > 1:
           step = int(step / 1.25)
       flag, i = False, 0
       while i + step < n:
          if ls[i] > ls[i + step]:
              ls[i], ls[i + step] = ls[i + step], ls[i]
              flag = True
          i += step
    return ls

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

function combSorting(array) {
  	var interval = Math.floor(array.length / 1.25);
  	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.25);
	}
}

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

public static void CombSort(byte[] bytes, bool swapped = false, double factor = 1.25)
{
    ulong gap = (ulong)bytes.Length;
    
    while ((gap > 1) || swapped)
    {
        gap = (ulong)(gap / factor);
        if (gap < 1) gap = 1;
        ulong i = 0;
        ulong m = gap;
        swapped = false;
        while (m < (ulong)bytes.Length)
        {
            if (bytes[i] > bytes[m])
            {
                swapped = true;
                byte t = bytes[i];
                bytes[i] = bytes[m];
                bytes[m] = t;
            }
            i++;
            m = i + gap;
        }
    }
}