Shell Sort (Сортировка Шелла)

Краткое описание

Обобщение Insertion Sort, которое сравнивает и обменивает элементы на больших расстояниях (gap), постепенно уменьшая это расстояние до 1. Позволяет элементам быстро перемещаться к их финальной позиции, преодолевая главный недостаток Insertion Sort — медленное перемещение элементов на большие расстояния.

Когда использовать

• Средние массивы (сотни-тысячи элементов) — эффективнее простых O(n²) алгоритмов, но проще чем Quick/Merge Sort
• Ограниченная память — использует O(1) дополнительной памяти (in-place)
• Нет рекурсии — подходит для систем с ограниченным стеком
• Простота реализации важна — проще чем Quick Sort или Merge Sort, но эффективнее базовых алгоритмов
• Встроенные системы — хорошая производительность без сложного кода
• Почти отсортированные данные — работает эффективно благодаря основе на Insertion Sort

Когда не стоит использовать:

• Очень большие массивы — Quick Sort, Merge Sort или IntroSort будут эффективнее
• Нужна стабильность — Shell Sort не стабильный алгоритм
• Нужна гарантированная производительность — сложность зависит от последовательности gap (может быть от O(n log² n) до O(n²))
• Критична предсказуемость — производительность сильно зависит от выбора последовательности gap

---

С объяснением логики работы

/**
 * Shell Sort — улучшенная версия Insertion Sort
 * 
 * Идея:
 * 1. Insertion Sort медленно перемещает элементы (по одной позиции за раз)
 * 2. Shell Sort сначала сравнивает далёкие элементы (gap > 1)
 * 3. Постепенно уменьшаем gap до 1
 * 4. Последний проход с gap=1 — это обычный Insertion Sort, но массив уже почти отсортирован
 */
 
/**
 * Shell Sort с последовательностью gap Knuth (1, 4, 13, 40, 121, ...)
 * Формула: gap = (3^k - 1) / 2
 * Это одна из лучших последовательностей для Shell Sort
 */
function shellSort(arr) {
    const n = arr.length;
 
    // ШАГ 1: Вычисляем начальный gap по формуле Кнута
    // Начинаем с максимального gap < n
    // Последовательность Knuth: 1, 4, 13, 40, 121, 364, 1093...
    let gap = 1;
    while (gap < Math.floor(n / 3)) {
        gap = gap * 3 + 1;  // Следующий gap в последовательности
    }
 
    // ШАГ 2: Проходы с уменьшающимся gap
    while (gap >= 1) {
 
        // ШАГ 3: Для текущего gap выполняем "gapped insertion sort"
        // Это как Insertion Sort, но сравниваем элементы на расстоянии gap
 
        // Проходим по всем элементам начиная с gap-й позиции
        for (let i = gap; i < n; i++) {
 
            // Сохраняем текущий элемент для вставки
            const temp = arr[i];
 
            // Это будет индекс для сравнения с элементами на расстоянии gap
            let j = i;
 
            // КЛЮЧЕВАЯ ИДЕЯ: сравниваем arr[j] с arr[j-gap], а не с arr[j-1]
            // Сдвигаем элементы с шагом gap, пока не найдём правильную позицию
            while (j >= gap && arr[j - gap] > temp) {
                // Сдвигаем элемент вправо на gap позиций
                arr[j] = arr[j - gap];
 
                // Переходим к следующему элементу на расстоянии gap
                j -= gap;
            }
 
            // Вставляем temp на найденную позицию
            arr[j] = temp;
        }
 
        // ШАГ 4: Уменьшаем gap для следующего прохода
        // По формуле Кнута: gap = (gap - 1) / 3
        gap = Math.floor(gap / 3);
    }
 
    // После последнего прохода с gap=1 массив полностью отсортирован
    return arr;
}
 
// Пример использования
const numbers = [64, 34, 25, 12, 22, 11, 90, 88];
console.log("Исходный массив:", numbers);
shellSort(numbers);
console.log("Отсортированный массив:", numbers);
 
/**
 * ВИЗУАЛИЗАЦИЯ РАБОТЫ на примере [64, 34, 25, 12, 22, 11, 90, 88]:
 * 
 * Начальный gap = 4:
 * Сравниваем: [64, _, _, _, 22]  [34, _, _, _, 11]  [25, _, _, _, 90]  [12, _, _, _, 88]
 * После gap=4: [22, 11, 25, 12, 64, 34, 90, 88]
 * 
 * gap = 1:
 * Выполняем обычный Insertion Sort, но массив уже почти отсортирован!
 * После gap=1: [11, 12, 22, 25, 34, 64, 88, 90]
 */
 
/**
 * ПОЧЕМУ SHELL SORT БЫСТРЕЕ INSERTION SORT:
 * 
 * Insertion Sort:
 * - Чтобы переместить 90 из начала в конец массива из 1000 элементов
 * - Нужно ~1000 сдвигов (по одной позиции)
 * 
 * Shell Sort:
 * - Первый проход с gap=364: переместит 90 на 364 позиции (1 сдвиг)
 * - Второй проход с gap=121: ещё 121 позиция (1 сдвиг)
 * - Третий проход с gap=40: ещё 40 позиций (1 сдвиг)
 * - И так далее...
 * - Итого: ~5-7 сдвигов вместо 1000!
 */
 
// Альтернативная реализация с последовательностью gap Shell (n/2, n/4, n/8, ...)
function shellSortOriginal(arr) {
    const n = arr.length;
 
    // Начинаем с gap = n/2 и делим пополам на каждом проходе
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
 
        for (let i = gap; i < n; i++) {
            const temp = arr[i];
            let j = i;
 
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
 
            arr[j] = temp;
        }
    }
 
    return arr;
}
 
// ПРИМЕЧАНИЕ: последовательность Knuth обычно даёт лучшие результаты,
// чем оригинальная последовательность Shell (n/2, n/4, ...)

---

С анализом сложностей

/**
 * Shell Sort с анализом сложности
 * 
 * ВРЕМЕННАЯ СЛОЖНОСТЬ (зависит от последовательности gap):
 * - Оригинальная (n/2, n/4, ...): O(n²) в худшем случае
 * - Knuth (3^k-1)/2:               O(n^(3/2)) ≈ O(n^1.5) в худшем
 * - Sedgewick:                     O(n^(4/3)) в худшем
 * - Лучший случай:                 O(n log n) для хороших последовательностей
 * 
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
 * - O(1) — только переменные gap, i, j, temp
 * - In-place сортировка
 * 
 * ОСОБЕННОСТИ:
 * - НЕ стабильный (элементы могут перепрыгивать через равные)
 * - Адаптивный (быстрее на почти отсортированных)
 * - Без рекурсии
 */
 
/**
 * Shell Sort с последовательностью Knuth
 * Сложность: O(n^(3/2)) в худшем случае
 */
function shellSortKnuth(arr) {
    const n = arr.length;
 
    // ВЫЧИСЛЕНИЕ НАЧАЛЬНОГО GAP: O(log n)
    // Последовательность Knuth: gap_k = (3^k - 1) / 2
    // Примеры: 1, 4, 13, 40, 121, 364, 1093, 3280, 9841...
    let gap = 1;
    while (gap < Math.floor(n / 3)) {
        gap = gap * 3 + 1;
    }
 
    // КОЛИЧЕСТВО ПРОХОДОВ: O(log n)
    // Каждый проход уменьшает gap в ~3 раза
    // Для n=1000: gap = 364 → 121 → 40 → 13 → 4 → 1 (6 проходов)
    while (gap >= 1) {
 
        // ПРОХОД С ТЕКУЩИМ GAP
        // Сложность одного прохода зависит от gap:
        // - Для большого gap: меньше сравнений и сдвигов
        // - Для gap=1: O(n) на почти отсортированном массиве
 
        for (let i = gap; i < n; i++) {
            // Внешний цикл: O(n)
 
            const temp = arr[i];
            let j = i;
 
            // Внутренний цикл: количество итераций зависит от gap и данных
            // 
            // АНАЛИЗ СЛОЖНОСТИ:
            // - Для gap близкого к n: мало элементов для сравнения
            // - Для gap=1 на почти отсортированном: O(1) итераций в среднем
            // - Суммарная работа всех проходов: O(n^(3/2)) для Knuth
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
 
            arr[j] = temp;
        }
 
        // Уменьшаем gap: O(1)
        gap = Math.floor(gap / 3);
    }
 
    return arr;
}
 
/**
 * Shell Sort с оригинальной последовательностью Shell
 * Сложность: O(n²) в худшем случае (хуже чем Knuth!)
 */
function shellSortOriginal(arr) {
    const n = arr.length;
 
    // КОЛИЧЕСТВО ПРОХОДОВ: O(log n)
    // Последовательность: n/2, n/4, n/8, ..., 1
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
 
        for (let i = gap; i < n; i++) {
            const temp = arr[i];
            let j = i;
 
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
 
            arr[j] = temp;
        }
    }
 
    return arr;
}
 
/**
 * Shell Sort с последовательностью Sedgewick
 * Одна из лучших последовательностей: O(n^(4/3)) в худшем случае
 * Последовательность (1986): 1, 5, 19, 41, 109, 209, 505, 929...
 * (генерируется рекуррентой в коде ниже: 9·4^k − 9·2^k + 1 для чётных k,
 *  8·2^k − 6·2^((k+1)/2) + 1 для нечётных k)
 */
function shellSortSedgewick(arr) {
    const n = arr.length;
 
    // Генерируем последовательность Sedgewick
    const gaps = [];
    let k = 0;
 
    while (true) {
        let gap;
        if (k % 2 === 0) {
            // Для чётных k: 9·4^k - 9·2^k + 1
            const pow4 = Math.pow(4, k / 2);
            const pow2 = Math.pow(2, k / 2);
            gap = 9 * pow4 - 9 * pow2 + 1;
        } else {
            // Для нечётных k: 8·2^k - 6·2^((k+1)/2) + 1
            const pow2k = Math.pow(2, k);
            const pow2half = Math.pow(2, (k + 1) / 2);
            gap = 8 * pow2k - 6 * pow2half + 1;
        }
 
        if (gap >= n) break;
        gaps.push(gap);
        k++;
    }
 
    // Проходы с убывающими gaps
    for (let g = gaps.length - 1; g >= 0; g--) {
        const gap = gaps[g];
 
        for (let i = gap; i < n; i++) {
            const temp = arr[i];
            let j = i;
 
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
 
            arr[j] = temp;
        }
    }
 
    return arr;
}
 
// СРАВНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ GAP:
 
// 1. ОРИГИНАЛЬНАЯ SHELL (n/2, n/4, ...):
//    ✗ Худший случай: O(n²)
//    ✓ Простая в реализации
//    Не рекомендуется для production
 
// 2. KNUTH (1, 4, 13, 40, ...):
//    ✓ Худший случай: O(n^1.5)
//    ✓ Простая формула
//    ✓ Хорошая на практике
//    Рекомендуется как стандарт
 
// 3. SEDGEWICK:
//    ✓ Худший случай: O(n^(4/3))
//    ✓ Лучшая теоретическая сложность
//    ✗ Сложнее в реализации
//    Рекомендуется для критичных приложений
 
// ПРИМЕРЫ ПРОИЗВОДИТЕЛЬНОСТИ:
 
// Для n = 1000:
// - Insertion Sort: ~500,000 операций (O(n²))
// - Shell Sort (Knuth): ~15,000 операций (O(n^1.5))
// - Quick Sort: ~10,000 операций (O(n log n))
 
// Для n = 10,000:
// - Insertion Sort: ~50,000,000 операций
// - Shell Sort (Knuth): ~500,000 операций
// - Quick Sort: ~130,000 операций
 
/**
 * КОГДА SHELL SORT ЭФФЕКТИВЕН:
 * 
 * 1. РАЗМЕР ДАННЫХ: сотни-тысячи элементов
 *    - Слишком большой для O(n²) алгоритмов
 *    - Не требует сложности Quick/Merge Sort
 * 
 * 2. ОГРАНИЧЕНИЯ ПАМЯТИ
 *    - O(1) как у Insertion Sort
 *    - Нет рекурсии как у Quick Sort
 * 
 * 3. ПРОСТОТА КОДА
 *    - Проще Quick Sort и Merge Sort
 *    - Эффективнее простых алгоритмов
 * 
 * 4. ВСТРОЕННЫЕ СИСТЕМЫ
 *    - Предсказуемое использование памяти
 *    - Без рекурсии
 */
 
// Тестирование производительности
function benchmark() {
    const sizes = [100, 1000, 10000];
 
    sizes.forEach(n => {
        const arr = Array.from({length: n}, () => Math.floor(Math.random() * n));
 
        console.time(`Shell Sort (Knuth) n=${n}`);
        shellSortKnuth([...arr]);
        console.timeEnd(`Shell Sort (Knuth) n=${n}`);
 
        console.time(`Shell Sort (Original) n=${n}`);
        shellSortOriginal([...arr]);
        console.timeEnd(`Shell Sort (Original) n=${n}`);
 
        console.time(`Shell Sort (Sedgewick) n=${n}`);
        shellSortSedgewick([...arr]);
        console.timeEnd(`Shell Sort (Sedgewick) n=${n}`);
    });
}
 
// benchmark();