Метка: рекурсивные алгоритмы

Быстрая сортировка — один из самых эффективных алгоритмов сортировки с средней сложностью O(n log n). В этой статье разберём принцип работы и реализации на PHP и JavaScript.

📌 Принцип работы Quick Sort

• Выбор опорного элемента (pivot)
• Разделение массива на две части: элементы меньше pivot и больше pivot
• Рекурсивная сортировка обеих частей

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

<?php
function quickSort(array $arr): array {
    if (count($arr) <= 1) {
        return $arr;
    }
    
    $pivot = $arr[0];
    $left = $right = [];
    
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

// Пример использования
$array = [10, 80, 30, 90, 40, 50, 70];
$sorted = quickSort($array);
print_r($sorted);
?>

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

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

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[0];
    const left = [];
    const right = [];
    
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    
    return [...quickSort(left), pivot, ...quickSort(right)];
}

// Пример использования
const array = [10, 80, 30, 90, 40, 50, 70];
console.log(quickSort(array));

2. Оптимизированная версия (in-place)

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return;
    
    const pivot = partition(arr, left, right);
    quickSortInPlace(arr, left, pivot - 1);
    quickSortInPlace(arr, pivot + 1, right);
    
    return arr;
}

function partition(arr, left, right) {
    const pivot = arr[right];
    let i = left;
    
    for (let j = left; j < right; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    
    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
}

// Пример использования
const nums = [10, 80, 30, 90, 40, 50, 70];
console.log(quickSortInPlace([...nums]));

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

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

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

• Преимущества:
  • Обычно быстрее других алгоритмов на практике
  • Требует мало дополнительной памяти
  • Хорошо работает с кэшем процессора
• Недостатки:
  • Худший случай O(n²) (редко при правильном выборе pivot)
  • Нестабильный

Оптимальное применение: сортировка больших массивов в памяти, когда стабильность не важна.

🔍 Дополнение: Нестабильность Quick Sort на практике

Критически важное отличие Quick Sort от стабильных алгоритмов вроде Merge Sort — его нестабильность. Это означает, что при наличии одинаковых элементов их относительный порядок после сортировки может измениться.

Наглядный пример

// Данные: пользователи с одинаковым возрастом
const users = [
  { name: 'Анна', age: 25 },
  { name: 'Иван', age: 30 },
  { name: 'Мария', age: 25 } // Такое же значение age, как у Анны
];

// После Quick Sort возможен вариант:
[
  { name: 'Мария', age: 25 }, // Мария теперь перед Анной!
  { name: 'Анна', age: 25 },
  { name: 'Иван', age: 30 }
]

Когда это критично?

• При сортировке таблиц по нескольким столбцам (например: сначала по дате, потом по имени)
• В финансовых системах, где важен порядок операций с одинаковой суммой
• При работе с хронологическими данными (новости, события)

Как решить проблему?

1. Добавить индекс сравнения:
   

   arr.map((item, index) => ({ ...item, _index: index }))
   // Сортировка с учётом _index при равенстве

2. Использовать стабильные аналоги:
   • Merge Sort
   • Встроенный Array.prototype.sort() (стабилен в современных браузерах)
   • Timsort (Python, Java)

Ситуация	Рекомендация
Важна скорость + нет одинаковых ключей	Quick Sort (оптимальный выбор)
Работа с объектами/дублями	Merge Sort или встроенная сортировка
Ограниченная память	In-place Quick Sort (но без стабильности)

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