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

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

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

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

Алгоритм[править | править код]

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

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

Реализация на Паскаль[править | править код]

  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++[править | править код]

    int comb(vector<double> sort)// sort-название массива, size-размер массива,если нужно ввести массив с клавиатуры, то нужно создать динамический массив
    {
        int n = 0; // количество перестановок
		double fakt = 1.2473309; // фактор уменьшения
		double step = sort.size() - 1;

		while (step >= 1)
		{
			for (int i = 0; i + step < sort.size(); ++i)
			{
				if (sort[i] > sort[i + step])
				{
					swap(sort[i], sort[i + step]);
					n++;
				}
			}
			step /= fakt;
		}
		// сортировка пузырьком
		for (int i = 0; i < sort.size() - 1; i++)
		{
			bool swapped = false;
			for (int j = 0; j < sort.size() - i - 1; j++)
			{
				if (sort[j] > sort[j + 1]) {
					swap(sort[j], sort[j + 1]);
					swapped = true;
					++n;
				}
			}

			if (!swapped)
				break;
		}
		return n;
	}

Реализация на 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
    return alist

Реализация на JavaScript[править | править код]

function combSorting(array) {
  const factor = 1.247;
  let gapFactor = array.length / factor;
  
  while (gapFactor > 1) {
    const gap = Math.round(gapFactor);
    for (let i = 0, j = gap; j < array.length; i++, j++) {
      if (array[i] >= array[j]) {
        [ array[i], array[j] ] = [ array[j], array[i] ];
      }
    }
    gapFactor = gapFactor / factor;
  }
  
  return array;
}

Примечания[править | править код]

  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.