Дисклеймер
Інформація на сайті tseivo.com є суб'єктивною та відображає особисті погляди та досвід авторів та авторок блогів.
Використовуйте цей ресурс як одне з декількох джерел інформації під час своїх досліджень та прийняття рішень. Завжди застосовуйте критичне мислення. Людина сама несе відповідальність за свої рішення та дії.
Що таке QuickSort? Коли та ким створений? Як саме працює QuickSort?
QuickSort є алгоритмом сортування, який використовує стратегію "розділяй і володарюй". Він швидко та ефективно сортує масиви шляхом порівняння елементів та переміщення їх на потрібні позиції.
Коли та ким створений QuickSort?
QuickSort був розроблений британським інженером і інформатиком Тоні Хоаром (Tony Hoare) у 1959 році. Тоні Хоар став відомим в галузі комп'ютерних наук завдяки своїм значним внескам, а QuickSort став одним з його найбільш відомих винаходів. Тоні Хоар отримав премію Тюрінга (Turing Award) в 1980 році за свої роботи в галузі сортування та аналізу алгоритмів.
Як саме працює сортування QuickSort?
- Обирається опорний елемент (поріг). Це може бути будь-який елемент масиву, наприклад, перший, останній або середній елемент.
- Розташовуємо елементи масиву таким чином, що всі елементи менші за поріг розміщуються перед ним, а всі більші елементи - після нього. Опорний елемент потрапляє на свою фінальну позицію.
- Рекурсивно застосовуємо QuickSort до підмасиву, що знаходиться перед опорним елементом (менших елементів) та підмасиву, що знаходиться після опорного елементу (більших елементів).
- Повторюємо кроки 1-3 для кожного підмасиву, поки весь масив не буде відсортований.
Оскільки QuickSort застосовує стратегію "розділяй і володарюй", він демонструє гарну швидкість роботи. У середньому, його складність O(n log n), де n - кількість елементів у масиві. Проте, найгірший випадок може мати складність O(n^2), коли опорний елемент завжди вибирається як найбільший або найменший елемент масиву. Для уникнення найгіршого випадку, можуть використовуватись різні стратегії вибору опорного елемента, наприклад, випадковий вибір або медіана трьох елементів.
Приклад QuickSort алгоритму (JavaScript).
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[Math.floor(arr.length / 2)];
const less = [];
const greater = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
less.push(arr[i]);
} else if (arr[i] > pivot) {
greater.push(arr[i]);
}
}
return [...quickSort(less), pivot, ...quickSort(greater)];
}
// Приклад використання:
const array = [5, 3, 1, 6, 2, 4];
const sortedArray = quickSort(array);
console.log(sortedArray);
Функція quickSort приймає масив arr як вхідний параметр і повертає відсортований масив.
Алгоритм QuickSort рекурсивно розділяє вхідний масив на менші і більші підмасиви відносно обраного опорного елемента (pivot). Елементи, менші за pivot, зберігаються у less, а більші - у greater. Потім викликається рекурсивний виклик quickSort для підмасивів less і greater, а результати об'єднуються з опорним елементом pivot для формування кінцевого відсортованого масиву.
Результат:
[1, 2, 3, 4, 5, 6]
Приклад QuickSort алгоритму (Ruby).
def quick_sort(arr)
return arr if arr.length <= 1
pivot = arr[arr.length / 2]
less = []
greater = []
arr.each do |element|
if element < pivot
less << element
elsif element > pivot
greater << element
end
end
return [*quick_sort(less), pivot, *quick_sort(greater)]
end
# Приклад використання:
array = [5, 3, 1, 6, 2, 4]
sorted_array = quick_sort(array)
puts sorted_array
Так саме як й у прикладі з JavaScript - функція quick_sort приймає масив arr як вхідний параметр і повертає відсортований масив.
Алгоритм QuickSort рекурсивно розділяє вхідний масив на менші і більші підмасиви відносно обраного опорного елемента (pivot). Елементи, менші за pivot, зберігаються у масиві less, а більші - у масиві greater. Потім рекурсивно викликається quick_sort для підмасивів less і greater, а результати об'єднуються з опорним елементом pivot за допомогою оператора распаковки * для формування кінцевого відсортованого масиву.
Результат:
[1, 2, 3, 4, 5, 6]
Чи використовується QuickSort алгоритм у стандартних методах JavaScript aбо Ruby?
У стандартних методах мови Ruby та JavaScript, які відповідають за сортування, зазвичай не використовується точно QuickSort алгоритм. Це може варіюватися в залежності від конкретної реалізації мови та її версії, а також від унікальних вимог та оптимізацій, які використовуються.
У Ruby для сортування масивів за замовчуванням використовується алгоритм, який поєднує методи QuickSort, InsertionSort та HeapSort. Цей алгоритм називається Timsort, який був розроблений для оптимального сортування різних типів даних.
У JavaScript сортування масивів зазвичай виконується за допомогою методу Array.prototype.sort(). Імплементація цього методу може варіюватися між різними реалізаціями JavaScript (наприклад, двигунами V8 в Node.js або Chrome і SpiderMonkey в Firefox). В більшості випадків, для сортування використовується швидкий і оптимізований алгоритм, який поєднує QuickSort з InsertionSort або MergeSort, залежно від реалізації.
Отже, хоча QuickSort може бути використаний як один з компонентів або базових алгоритмів у методах сортування масивів Ruby і JavaScript, сам по собі QuickSort не є єдиним алгоритмом, що використовується в цих мовах для сортування за замовчуванням. Зазвичай використовуються більш складні алгоритми, такі як Timsort або його варіації, які поєднують різні алгоритми сортування для забезпечення оптимальності та широкого спектру випадків використання.
📝 Більше публікацій: