Ошибки в сортировке расческой

Question

Прочитал статью про сортировку расческой https://thecode.media/comb-sort/, протестировал код и оказалось, что при значениях factor больше 1.31 код начинает неправильно работать, хотя в статье об этом ничего не говорилось. Почему это начинает происходить именно с такого значения, а не с 1.2 или 1.4?

// исходный массив 
var arr = [];
for(let i = 0;i < 1000;i++){
    arr.push(Math.random());
}

// получаем длину массива
const l = arr.length;
// оптимальное число для вычисления шага сравнения
const factor = 1.32;
// получаем точный шаг сравнения
let gapFactor = l / factor;
// пока шаг больше единицы
while (gapFactor > 1) {
    // округляем шаг до целого
    const gap = Math.round(gapFactor);
    // и организуем цикл как в пузырьковой сортировке
    for (let i = 0, j = gap; j < l; i++, j++) {
        // если сначала идёт большое число
        if (arr[i] > arr[j]) {
            // меняем их местами
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
        // выводим текущее состояние массива в консоль 
        // это необязательный шаг, он здесь для наглядности 
        //console.log(arr);
    }
    // в конце цикла рассчитываем новый шаг
    gapFactor = gapFactor / factor;
}

for(let i = 0;i < arr.length - 1;i++){
    if(arr[i + 1] < arr[i]){
        console.log('Массив неправильно отсортирован! ' + i);
    }
}

Answer 1

Дело в том, что один проход пузырьковой сортировки не обеспечивает полную сортировку.

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

А лучше добавить проверку того, что сортировка закончена - в условиях, когда элементы близко к своим местам, это будет быстрее.

Онлайн проверка

var arr = [];
for(let i = 0;i < 100;i++){
    arr.push(Math.round(Math.random()*1000));
}

const l = arr.length;

const factor = 1.7;

let gap = l;
let swaps = true;

// пока шаг больше единицы и были обмены
while ((gap > 1) || swaps) {
    gap = Math.max(1, Math.round(gap / factor));
    swaps = false;
    for (let i = 0; i+gap < l; i++) {
        if (arr[i] > arr[i+gap]) {
            let t = arr[i+gap];
            arr[i+gap] = arr[i];
            arr[i] = t;
            swaps = true;
        }
       //print(arr);
    }
}

for(let i = 0;i < arr.length - 1;i++){
    if(arr[i + 1] < arr[i]){
        print('Массив неправильно отсортирован! ' + i + ' ' + arr[i] + ' ' +arr[i+1]);
    }
}

БЛОГ НА HUSL

Ошибки в сортировке расческой

Ответы (1 шт):