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

Сортировка расчёской ( англ. comb sort ) — это довольно ^{[

уточнить

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

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

Алгоритм

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

источник не указан 1660 дней

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

Оптимальное значение фактора уменьшения $1{,}24733...={\tfrac {1}{1-e^{-\Phi }}}$ , где $e$ — основание натурального логарифма , а $\Phi =1{,}61803...$ — золотое сечение .

Реализация

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

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

const int N = 100;
int a[N];
double factor = 1.2473309;
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.2473309);
    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++

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(ls):
    n = len(ls)
    step = n
    while step > 1 or flag:
       if step > 1:
           step = int(step / 1.247331)
       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.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);
	}
}

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

public static void CombSort(byte[] bytes, bool swapped = false, double factor = 1.2473309)
{
    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;
        }
    }
}

Примечания

Lacey S., Box R. A Fast, Easy Sort: A novel enhancement makes a bubble sort into one of the fastest sorting routines (англ.) // . — Апрель 1991. — Vol. 16, no. 4 . — P. 315—320. — ISSN .

[1] Lacey S., Box R. A Fast, Easy Sort: A novel enhancement makes a bubble sort into one of the fastest sorting routines (англ.) // . — Апрель 1991. — Vol. 16, no. 4 . — P. 315—320. — ISSN .

Алгоритмы сортировки
Теория	Сложность О-нотация Отношение порядка Типы сортировки Устойчивая Внутренняя Внешняя
Обменные	Пузырьком Перемешиванием Гномья Быстрая Сортировка чёт-нечет Поразрядная
Выбором	Выбором Пирамидальная Плавная
Вставками	Вставками Шелла Деревом
Слиянием	Слиянием
Без сравнений	Подсчётом Блочная
Гибридные	Introsort Timsort
Прочее	Топологическая Сети Битонная
Непрактичные	Bogosort Stooge sort Блинная Медленная