З часу відкриття сортувальної машини Холлеріта у 1901-1904, більшість ЕОМ використовували порозрядний алгоритм сортування. Цей алгоритм має кращі показники часу, ніж більшість сучасних алгоритмів сортування, однак може працювати лише з ключами фіксованої довжини, до того ж він погано масштабується – має змінні вимоги до потрібних ресурсів пам’яті.
Через це проблема швидкого сортування була і залишається одною з найважчих проблем інформатики – алгоритму, який мав би сталий час виконання, постійні вимоги до пам’яті, одночасно з умінням стабільного сортування і не потребував частково відсортованого масиву просто не існує. Але є один алгоритм, який своїми характеристиками і простотою реалізації вже більше 50 років завойовує серця програмістів.
Прямою передумовою до появи алгоритму Quicksort стало вивчання Чарльзом Ентоні Гоаром комп’ютерного перекладу з російської на англійську під керівництвом А.Н.Колмогорова у Московському Державному Університеті. Проблема полягала в тому, що всі словники зберігалися на магнітних плівках, а тому йому доводилося сортувати слова в реченнях перед перекладом.
Гоар придумав два методи для вирішення цієї проблеми. Перший метод вимагав часу пропорційно до квадрату від довжини речення, другий метод пізніше було названо quicksort. На той час Гоар знав лише одну мову програмування – Mercury Autocode. На жаль, успішно запрограмувати алгоритм за цією мовою не вдалося.
Через ускладнену політичну ситуацію Чарльзу довелося покинути Радянський Союз, а через рік (1961 року) він відвідав курс Algol 60 у Брайтоні.
Одним з головних нововведень Algol 60 була рекурсія (можливість процедури викликати саму себе). Під час цього курсу Гоару вдалося запрограмувати свій супершвидкий алгоритм, який зараз відомий як quicksort. Того ж року він видав наукову доповідь на цю тему, яка називалася “Algorithm 64: Quicksort” та містила комплексне дослідження алгоритму Quicksort.
Оригінальний алгоритм мав свої недоліки, але простота імплементації, змога працювати з будь-якими даними і використання мінімуму ресурсів перемогли, і багато іменитих програмістів та фахівців у сфері комп’ютерних наук почали роботу над покращенням алгоритму.
Quicksort – це алгоритм, який базується на принципі “розділяй та володарюй”. Для сортування масиву даних А, він розбиває масив на дві частини і переносить маленькі елементи на ліву його частину, а великі на праву. Після цього алгоритм сортує отримані підмасиви рекурсивно.
Алгоритм досліджували багато відомих вчених, які зробили його таким, який він є сьогодні. Наприклад, професор Прінстонського університету Роберт Седжвік, про якого мали чути майже всі студенти спеціальності Інформатика, брав участь у подальших правках цього алгоритму, а також зробив його темою своєї докторської дисертації.
З моменту відкриття Гоаром у 1961, алгоритм Quicksort пережив багато модифікацій. Більшість з них направлялися на боротьбу з часом найгіршого випадку . Загалом, модифікації можна розділити на чотири категорії: покращення умов вибору опорного елементу; алгоритми, які використовують інші алгоритми для сортування конкретних випадків розміру масиву; різні способи розділення масивів і адаптивне сортування, яке намагається покращити поведінку алгоритму Quicksort, коли відбувається сортування мйже відсортованого масиву. Четвертій категорії присвячено цілі книги.
Над алгоритмом Quicksort працювали і продовжують працювати багато іменитих і не дуже вчених. Над ним працювали Седжвік та Дейкстра, який активно поширював його серед своїх студентів, та й до того ж, будь-який студент-програміст під час вивчення структур даних більше всього любить саме Quicksort, що іноді призводить до проривних відкриттів на цю тему – модифікований з цікавості алгоритм може показувати хороші результати.
Дослідження алгоритма не зупиняється і до сьогодні, а оригінальний варіант Quicksort 1961 року іноді можна зустріти на Github у реальних проектах.
Саме цей алгоритм завдяки своїм супершвидким і ефективним показникам дозволив економити на ресурсах комп’ютерів, саме він почав культ підвищення ефективності коду замість нівеляції складності задачі ресурсами комп’ютерів. “Можна витратити мільйон на суперкомп’ютер, а можна модернізувати алгоритм” – Седжвік.
Вплив Quicksort на співтовариство програмістів по всьому світі настільки сильний, що будь-хто на даний момент може навіть замовити собі футболку з прінтом реалізації оригіналу алгоритму на улюбленій мові програмування.
Джерела
1. J. Bentley, “Programming Pearl: How to sort”, Com.. ACM, Vol. 27 Issue 4, April 1984
2. R. Sedgewick, Algorithms in C++, 3 rd edition, Addison Wesley, 1998.
3. Stanford — About Quicksort. [Електронний ресурс]. Режим доступу: http://cs.stanford.edu/people/eroberts/courses/soco/projects/2008-09/tony-hoare/quicksort.html
4. C. Martinez, Partial quicksort. In Proceedings of the First ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 2004.
5. Princeton — About Quicksort. [Електронний ресурс]. Режим доступу: http://algs4.cs.princeton.edu/23quicksort/
6. QuickSort A Historical Perspective and Empirical Study, Laila Khreisat Dept. of Computer Science, Math and Physics Fairleigh Dickinson University
7. Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort. [Електронний ресурс]. Режим доступу: http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
8. Stackoverflow — Why Collections.sort uses merge sort instead of quicksort? [Електронний ресурс]. Режим доступу: http://stackoverflow.com/questions/15154158/why-collections-sort-uses-merge-sort-instead-of-quicksort
9. Princeton — Quicksort lection. [Електронний ресурс]. Режим доступу: http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf
Статтю підготував студент ІІІ курсу спеціальності інформатика Гавриленко Кирило Олегович у межах звіту про вивчення курсу «Історія науки і техніки» (викладач – професор Р.Я.Ріжняк).