Сортировка расчёской(гребешком) кратко

Привет, Вы узнаете о том , что такое сортировка расчёской, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое сортировка расчёской, сортировка гребешком , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

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

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

Алгоритм

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

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

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

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

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

Данная статья про сортировка расчёской подтверждают значимость применения современных методик для изучения данных проблем. Надеюсь, что теперь ты понял что такое сортировка расчёской, сортировка гребешком и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов