вторник, 20 сентября 2011 г.

Быстрая сортировка (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).

Комментариев нет:

Отправить комментарий