Швидке сортування

9.1 Визначення швидкого сортування.

Швидке сортування (Quick Sort) — це ефективний алгоритм сортування, який використовує підхід "розділяй і володарюй". Він працює шляхом вибору опорного елемента (pivot), розподілу масиву на два підмасиви — елементи, менші за опорний, і елементи, більші за опорний, а потім рекурсивного застосування того ж процесу до кожного підмасиву.

Алгоритм швидкого сортування з'явився як спроба вирішити проблему «як можна швидше перекинути вліво маленькі елементи, а вправо – великі». Припустимо, у нас найменший елемент - крайній справа, чи можна якось швидко перекинути його, якщо не на його фінальну позицію, то близько до неї? Це б сильно зменшило кількість непотрібних порівнянь.

Принцип роботи:

1. Вибір опорного елемента (pivot):

Обираємо елемент з масиву як опорний. Це може бути перший елемент, останній елемент, середній елемент або випадковий елемент. Іноді це середнє арифметичне трьох випадкових елементів.

2. Розділення (partitioning):

Переміщуємо всі елементи, менші за опорний, в ліву частину масиву, а всі елементи, більші за опорний, — в праву частину. У результаті опорний елемент опиняється на своєму остаточному місці в відсортованому масиві.

3. Рекурсивне застосування:

Рекурсивно застосовуємо процес до лівого та правого підмасивів, не включаючи опорний елемент.

Покроковий процес

1. Вибираємо опорний елемент.
2. Переміщуємо елементи, менші за опорний, вліво, а елементи, більші — вправо.
3. Рекурсивно застосовуємо процес до підмасивів.

Часова і просторова складність швидкого сортування

Часова складність:

• У найгіршому випадку: O(n^2) — відбувається, коли кожного разу вибирається найгірший опорний елемент (наприклад, коли масив вже відсортований).
• У середньому випадку: O(n log n) — для випадково розподілених даних.
• У найкращому випадку: O(n log n) — коли масив кожного разу ділиться на рівні частини.

Просторова складність:

O(log n) — потрібно для зберігання стека викликів рекурсії, якщо використовується хвостова рекурсія і опорні елементи обираються вдало.

9.2 Реалізація алгоритму швидкого сортування.

Реалізація на Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return  arr  # Базовий випадок: масив з 0 або 1 елементом вже відсортований
            
    pivot = arr[len(arr) // 2]  # Обираємо опорний елемент
    left = [x for x in arr if x < pivot]  # Елементи, менші за опорний
    middle = [x for x in arr if x == pivot]  # Елементи, рівні опорному
    right = [x for x in arr if x > pivot]  # Елементи, більші за опорний
            
    return quick_sort(left) + middle + quick_sort(right)
        
# Приклад використання:
arr = [3, 6, 8, 10, 1, 2, 1]
print("Відсортований масив:", quick_sort(arr))
        

Приклад роботи алгоритму

Візьмемо приклад масиву: [3, 6, 8, 10, 1, 2, 1]

Перший прохід:

• Опорний елемент: 8
• Ліві елементи: [3, 6, 1, 2, 1]
• Середні елементи: [8]
• Праві елементи: [10]

Рекурсивне сортування лівої частини [3, 6, 1, 2, 1]:

• Опорний елемент: 1
• Ліві елементи: []
• Середні елементи: [1, 1]
• Праві елементи: [3, 6, 2]

Рекурсивне сортування правої частини [3, 6, 2]:

• Опорний елемент: 6
• Ліві елементи: [3, 2]
• Середні елементи: [6]
• Праві елементи: []

Рекурсивне сортування лівої частини [3, 2]:

• Опорний елемент: 2
• Ліві елементи: []
• Середні елементи: [2]
• Праві елементи: [3]

Результат злиття: [1, 1, 2, 3, 6] для лівої частини, [10] для правої частини, і [8] для середньої.

Кінцевий відсортований масив: [1, 1, 2, 3, 6, 8, 10]