Метка: Merge sort

Полный гид по алгоритмам сортировки: от базовых до специализированных методов

В мире компьютерных наук существует более 50 различных алгоритмов сортировки, каждый из которых имеет уникальные характеристики и области применения. Давайте систематизируем эти методы и разберём их ключевые особенности.

1. Основные категории алгоритмов сортировки

1.1. Сравнительные сортировки

Эти алгоритмы основаны на попарном сравнении элементов:

Обменные сортировки (Bubble Sort, Comb Sort, Quick Sort) — меняют местами элементы в процессе работы
Сортировки вставками (Insertion Sort, Shell Sort) — последовательно вставляют элементы в отсортированную часть
Сортировки выбором (Selection Sort, Heap Sort) — последовательно выбирают экстремальные элементы
Гибридные методы (Timsort, Introsort) — комбинируют разные подходы

1.2. Целочисленные сортировки

Специализированные методы для чисел и данных с известными свойствами:

Быстрые сортировки (Counting Sort, Radix Sort, Bucket Sort) — используют свойства числовых ключей
Битовые сортировки (Bitonic Sort, American Flag Sort) — работают с битовыми представлениями
Гибридные числовые (Flash Sort, Postman Sort) — сочетают разные подходы

2. Подробный разбор ключевых алгоритмов

2.1. Эффективные сравнительные сортировки

QuickSort (1960, Тони Хоар):
Использует стратегию «разделяй и властвуй» с выбором опорного элемента. В среднем случае работает за O(n log n), но может деградировать до O(n²) при неудачном выборе pivot. Современные реализации используют:

Медиану трёх для выбора pivot
Переключение на Heap Sort при глубокой рекурсии
Оптимизацию для маленьких подмассивов

Timsort (2002, Тим Петерс):
Гибридный алгоритм, сочетающий Merge Sort и Insertion Sort. Особенности:

Выделяет уже отсортированные подпоследовательности (runs)
Оптимален для реальных данных с частичной упорядоченностью
Используется в Python и Java

2.2. Специализированные числовые сортировки

Radix Sort:
Поразрядная сортировка, которая обрабатывает цифры чисел от младших к старшим. Варианты:

LSD (Least Significant Digit) — от младших разрядов к старшим
MSD (Most Significant Digit) — от старших разрядов к младшим
Гибридные версии с переключением на другой алгоритм

Counting Sort:
Эффективен когда диапазон значений (k) много меньше количества элементов (n). Применяется как подпрограмма для Radix Sort.

3. Экзотические и узкоспециализированные методы

Сортировка Шелла — улучшенный вариант Insertion Sort с предварительными проходами
Гномья сортировка — любопытный алгоритм, похожий на Bubble Sort
Bogosort — теоретический алгоритм с O(n!) сложностью
Сортировка слиянием на месте — сложная модификация без дополнительной памяти
Сортировка с помощью красно-чёрных деревьев — демонстрационный алгоритм

4. Критерии выбора алгоритма

Критерий	Рекомендуемые алгоритмы
Общий случай	Timsort, QuickSort
Ограниченная память	HeapSort, In-place MergeSort
Частично отсортированные данные	InsertionSort, Timsort
Числовые данные	RadixSort, CountingSort
Параллельная обработка	BitonicSort, SampleSort
Стабильность	MergeSort, InsertionSort

5. Современные тенденции

Современные исследования в области сортировки сосредоточены на:

Алгоритмах для параллельных и распределённых систем
Адаптивных алгоритмах, учитывающих структуру данных
Гибридных подходах, автоматически выбирающих стратегию
Оптимизации для конкретных архитектур процессоров

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

15.05.2025

Сортировка слиянием (Merge Sort) на PHP и JavaScript

Сортировка слиянием — это эффективный алгоритм сортировки, работающий по принципу «разделяй и властвуй». Он обладает стабильностью и гарантированной сложностью O(n log n).

📌 Алгоритм сортировки слиянием

Разделение массива на две половины
Рекурсивная сортировка каждой половины
Слияние отсортированных половин

💻 Реализация на PHP

<?php
function mergeSort(array $arr): array {
    if (count($arr) <= 1) {
        return $arr;
    }
    
    $middle = (int)(count($arr) / 2);
    $left = mergeSort(array_slice($arr, 0, $middle));
    $right = mergeSort(array_slice($arr, $middle));
    
    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = [];
    $i = $j = 0;
    
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $result[] = $right[$j++];
        }
    }
    
    return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}

// Пример использования
$array = [38, 27, 43, 3, 9, 82, 10];
$sorted = mergeSort($array);
print_r($sorted);
?>

🌐 Реализация на JavaScript

1. Классическая версия

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    
    const middle = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, middle));
    const right = mergeSort(arr.slice(middle));
    
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    return result.concat(left.slice(i)).concat(right.slice(j));
}

// Пример использования
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array));

2. Версия с визуализацией шагов

function mergeSortWithSteps(arr, level = 0) {
    console.log(`${'  '.repeat(level)}Сортируем:`, arr);
    
    if (arr.length <= 1) {
        console.log(`${'  '.repeat(level)}Базовый случай:`, arr);
        return arr;
    }
    
    const middle = Math.floor(arr.length / 2);
    const left = mergeSortWithSteps(arr.slice(0, middle), level + 1);
    const right = mergeSortWithSteps(arr.slice(middle), level + 1);
    
    const merged = merge(left, right);
    console.log(`${'  '.repeat(level)}Сливаем ${left} и ${right} →`, merged);
    
    return merged;
}

const nums = [5, 2, 4, 7, 1];
console.log("Исходный массив:", nums);
console.log("Результат:", mergeSortWithSteps(nums));

⚡ Сравнение с другими алгоритмами

Характеристика	Merge Sort	Quick Sort	Bubble Sort
Сложность (средняя)	O(n log n)	O(n log n)	O(n²)
Сложность (худшая)	O(n log n)	O(n²)	O(n²)
Память	O(n)	O(log n)	O(1)
Стабильность	Да	Нет	Да

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

Плюсы Merge Sort:
- Гарантированная сложность O(n log n)
- Стабильность (сохраняет порядок равных элементов)
- Хорош для связных списков и внешней сортировки
Минусы:
- Требует дополнительной памяти O(n)
- Медленнее Quick Sort на небольших массивах

Оптимальное применение: большие массивы (от 10k элементов), где важна стабильность.

Другие виды сортировок

Quick Sort — быстрая сортировка
Bubble Sort — сортировка пузырьком

14.05.2025