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)*[Sums=1~n(T(s) + T(n-s))] + cn

Worst:
O(n2) — 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(n2)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License