Швидке сортування. 
Паралельні і розподілені обчислення

Швидке сортування (англ. quicksort), часто звана qsort на ім'я реалізації в стандартній бібліотеці мови Сі - широко відомий алгоритм сортування, розроблений англійським інформатиком Чарльзом Хоаром в МДУ в 1960 році. Один з швидких відомих універсальних алгоритмів сортування масивів (в середньому O (n log n) обмінів при упорядкуванні n елементів), хоча і має ряд недоліків.

Швидке сортування використовує стратегію «розділяй і володарюй». Кроки алгоритму такі:

• — вибираємо в масиві певний елемент, який будемо називати опорним елементом. З точки зору коректності алгоритму вибір опорного елемента байдужий. З точки зору підвищення ефективності алгоритму вибиратися повинна медіана, але без додаткових відомостей про сортируемих даних її зазвичай неможливо отримати. Відомі стратегії: вибирати постійно один і той же елемент, наприклад, середній або останній за положенням; вибирати елемент з випадково вибраним індексом;
• — операція поділу масиву: реорганізуємо масив таким чином, щоб всі елементи зі значенням меншим або рівним опорному елементу, виявилися ліворуч від нього, а всі елементи, що перевищують за значенням опорний — праворуч від нього. Звичайний алгоритм операції:
• — два індекса — l і г, прирівнюються до мінімального і максимального індексу розділяється масиву, відповідно;
• — обчислюється індекс опорного елемента m;
• — індекс l послідовно збільшується до тих пір, поки l-й елемент не виявиться більше або дорівнює опорному;
• — індекс г послідовно зменшується до тих пір, поки г-й елемент не виявиться менше або дорівнює опорному;
• — якщо г = l — знайдена середина масиву — операція поділу закінчена, обидва індекси вказують на опорний елемент;
• — якщо l <�г — знайдену пару елементів потрібно обміняти місцями і продовжити операцію розділення з тих значень l і г, які були досягнуті. Слід врахувати, що якщо яка-небудь кордон (l або г) дійшла до опорного елемента, то при обміні значення m змінюється на г-й або l-й елемент відповідно, змінюється саме індекс опорного елемента і алгоритм продовжує своє виконання;
• — бекурсивно упорядковуємо подмассіви, що лежать ліворуч і праворуч від опорного елемента;
• — базою рекурсії є набори, які складаються з одного або двох елементів. Перший повертається в початковому вигляді, в другому, при необхідності, сортування зводиться до перестановки двох елементів. Всі такі відрізки вже впорядковані в процесі поділу.

Оскільки в кожній ітерації (на кожному наступному рівні рекурсії) довжина оброблюваного відрізка масиву зменшується, щонайменше, на одиницю, термінальна гілку рекурсії буде досягнута обов’язково і обробка гарантовано завершиться.