Quick Sort

There are various implementations of quick sort. Here is a way with very short codes.

void qsort(int *list, int left, int right) { int i, last; if (left < right) { swap(list, left, (left + right)/2); // swap the first node with the middle node last = left; for (i = left + 1; i <= right; i++) if (list[i] < list[left]) swap(list, ++last, i); swap(list, last, left); qsort(list, left, last - 1); qsort(list, last + 1, right); } }

In quick sort, we will get worst case when the input data is sorted.

Therefore, we swap the first node with the middle node, so we will get the best case when the input data is sorted. The best case happens when the new position of the pivot is always the middle of the array. Therefore, we need to compute pivot for logn time. n*logn -> O(nlogn)

## Time Complexity

Best:

O(nlogn) — every time when we try to find the new position of the pivot, it costs O(n).

Avg:

O(nlogn) — T(n) = (1/n)*[Sum_{s=1~n}(T(s) + T(n-s))] + cn

Worst:

O(n^{2}) — it happens when the array is already sorted. in this situation, the new location of the pivot is always in the head of the array. Therefore, we need to repeat the process for n time. -> n + n-1 + n-2 + … + 1 = O(n^{2})

page revision: 13, last edited: 30 Apr 2012 07:00