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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Реализация на C++[править | править вики-текст]

template <typename T, typename Comp>
void combsort(T array[ ], std::size_t size, Comp cmp) {
    if (array && size) {
        std::size_t jump = size;
        bool swapped = true;
        while (jump > 1 || swapped) {
            if (jump > 1)
                jump /= 1.24733;
            swapped = false;
            for (std::size_t i = 0; i + jump < size; ++i)
                if (cmp(array[i + jump], array[i])) {
                    std::swap(array[i], array[i + jump]);
                    swapped = true;
                }
        }
    }
}

Реализация на 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 combSorting(&$a) {
	$gap = $n = count($a);
	$swapped = true;
	while ($gap > 1 || $swapped) {
		if ($gap > 1) $gap = floor($gap / 1.24733);
		$i = 0;
		$swapped = false;
		while ($i + $gap < $n) {
			if ($a[$i] > $a[$i + $gap]) {
				list($a[$i], $a[$i + $gap]) = array($a[$i + $gap], $a[$i]);
				if (!$swapped) $swapped = true;
			}
			$i++;
		}
	}
}

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

  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. — № 4. — P. 315—320. — ISSN 0360-528.