Быстрая сортировка (Quick Sort) за O(NlogN) в среднем случае

[Все сортировки]

Теория: k-ая порядковая статистика 

Практика: informatics.mccme.ru

Визуализатор: youtube.com [Adobe Flash Player]

Реализация:

1. int partition(vector<int> &mas, int l, int r) {
2.   int pos = l-1;
3.   for (int i = l; i <= r; ++i) {
4.     if (mas[i] <= mas[r] )
5.       swap(mas[++pos], mas[i]);
6.   }
7.   return pos;
8. }
9. void quick_sort(vector<int> &mas, int l, int r) {
10.   if (l >= r) return;
11.   int pivot = partition(mas,l,r);
12.   quick_sort(mas,l,pivot-1);
13.   quick_sort(mas,pivot+1,r);
14. }

* This source code was highlighted with Source Code Highlighter.

Данная реализация на предложенной задаче работает в 2 раза быстрее(0.059 c), чем heap_sort(0.122 c).