https://ru.wikipedia.org/wiki/Сортировка_расчёской

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

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

Алгоритм сортировки

Производятся неоднократные проходы по массиву, при которых сравниваются пары элементов (изначально не соседние). Если они неотсортированы друг относительно друга — то производится обмен. В результате крупные элементы перемещаются в конец массива, а небольшие по значению — в начало.

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

Уменьшающееся расстояние между сравниваемыми элементами рассчитывается с помощью специальной величины, называемой фактором уменьшения. Длина массива делится на этот фактор, это и есть разрыв между индексами. После каждого прохода расстояние делится на фактор уменьшения и таким образом получается новое значение. В конце концов оно сужается до минимального значения — единицы, и массив просто досортировывается обычным «пузырьком».

В результате практических тестов и теоретических исследований оптимальное значение для фактора уменьшения определено следующее:

Визуализация работы алгоритма

Реализация алгоритма

static void CombSort(int[] arr)
{
    int n = 0; // количество перестановок
    double fakt = 1.2473309; // фактор уменьшения
    int step = arr.Length - 1;

    while (step >= 1)
    {
        for (int i = 0; i + step < arr.Length; ++i)
        {
            if (arr[i] > arr[i + step])
            {
                int temp = arr[i];
                arr[i] = arr[i + step];
                arr[i + step] = temp;
                n++;
            }
        }
        if (step == 1) break;
        step =(int)(step / fakt);
    }
}

Характеристики алгоритма