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

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

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

Визуализация сортировки расчёской
Предназначение Алгоритм сортировки
Худшее время O(n2)
Лучшее время O(n logn)
Среднее время
Затраты памяти O(1)
 Медиафайлы на Викискладе

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

Алгоритм

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

Оптимальное значение фактора уменьшения , где  — основание натурального логарифма, а  — золотое сечение.

Реализация в виде ассемблерной вставки на C++

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

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:"
    );
}

Реализация на языке Паскаль
  1. Заполняю массив случайными числами.
  2. Завожу цикл с условием «i < i + j», которое буквально означает «i отличается от i + j».
    1. Обнуляю i для того, чтобы при новом пробеге по массиву индекс не вышел за его границы.
    2. Завожу внутренний цикл с условием «i + j <= n», которое буквально значит «сумма индекса i и расстояния j между a[i] и другим сравниваемым элементом не больше, чем самый большой индекс массива».
      1. Если a[i] > a[i + j], то меняю их местами.
      2. Увеличиваю i.
    3. Уменьшаю 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);
	}
}

Примечания
  1. Lacey S., Box R. A Fast, Easy Sort: A novel enhancement makes a bubble sort into one of the fastest sorting routines (англ.) // Byte. — Апрель 1991. — Vol. 16, no. 4. — P. 315—320. — ISSN 0360-528.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.