Quick Sort

#########################
####   quick sort    ####
#########################

(ref)
http://en.wikipedia.org/wiki/Quicksort

(1) pick an element (pivot)
(2) shift smaller-than-pivot to one side, and bigger-than-pivot to the other. (equal to pivot can be in either group)
(3) recursively apply (1)(2) to each of the two sub groups until the input is one element.

there is more than one way to implement.

##############################
####   example iteration   ###
##############################

lets use this input list:  3 7 5 1 3 6 2 9 4

basic strategy is iterate from left & right.

(1) if ( (array[left] >= pivot && array[right] <= pivot) && left < right) then swap

3 7 5 1 3 6 2 9 4     # lets pick 4 as pivot
- ^             ^     # found 7(>=4), and 4(<=4)
3 4 5 1 3 6 2 9 7     # swapped 7 & 4
- - ^       ^ - -     # found 5(>=4), and 2(<=4)
3 4 2 1 3 6 5 9 7     # swapped 5 & 2
- - - - ^ ^ - - -     # found 6(>=4), and 3(<=4) but not gonna swap cos already crossed each other
# so once crossed, split into sub groups

sub group (1)
3 4 2 1 3             # lets pick 3 as pivot
^       ^
3 4 2 1 3             # swapped 3 & 3
- ^   ^ -
3 1 2 4 3             # swapped 4 & 1
- - ^ ^ -             # found 4 & 2,  but crossed. gonna split

sub group (1.1)
3 1 2                 # lets pick 2 as pivot
^   ^
2 1 3                 # swapped 3 & 2
- ^ ^                 # found 3 & 1, but crossed. gonna split

sub group (1.1.1)
2 1                   # lets pick 1 as pivot
^ ^
1 2                   # swapped 1 & 2
^ ^                   # found 2 & 1, but crossed. gonna split

sub group (1.1.1.1)
1                     # only one elem. nothing to do.
sub group (1.1.1.2)
2                     # only one elem.
sub group (1.1.2)
3                     # only one elem.
sub group (1.2)
4 3
3 4

sub group (2.1)
6 5 9 7               # lets pick 7 as pivot
- - ^ ^
6 5 7 9               # swapped 9 & 7
- - ^ ^               # found 9 & 7, but crossed. gonna split
sub group (2.1.1)
6 5 7                 # lets pick 7 as pivot
- - ^                 # found 7 & 7, but left == right, split
sub group (2.1.1.1)
6 5
5 6
sub group (2.1.1.2)

sub group (2.1.2)

1 2 3 3 4 5 6 7 9     #  this is the end result.

(2) if ( (array[left] >= pivot && array[right] < pivot) && left < right) then swap

lets take the same input list.

3 7 5 1 3 6 2 9 4     # lets pick 4 as pivot
- ^         ^ - -
3 2 5 1 3 6 7 9 4     # swapped 7 & 2
- - ^   ^ - - - -
3 2 3 1 5 6 7 9 4     # swapped 5 & 3
- - - ^ ^ - - - -     # found 5 & 1, but crossed, gonna split

3 2 3 1               # lets pick 3 as pivot
^     ^
1 2 3 3               # swapped 3 & 1
- ^ ^ -               # found 3 & 2, but crossed, gonna split

1 2                   # lets pick 1 as pivot
- ^                   # found 2(>= pivot) but cannot find a val smaller than pivot.
# this is the weakness of this method, so pick another pivot.
# infinite loop when you pick the smallest val as pivot that happens to sit on the left most
# and no other elems equal to pivot in the list

# implementation-wise, when the array length = 2, just compare and swap if needed, and terminate.

#########################
###  pivot selection  ###
#########################

ideal pivot is the median of the input elements. but to find the median, you need to iterate thru the input list, or sort it and search it somehow, etc, which can be too much computation cost for this algo.

the worst case is you split 1:N-1 or N-1:1

as seen in the above example, you get an infinite loop when you pick the smallest val as pivot that happens to sit on the left most and no other elems equal to pivot in the list

a few commonly used methods;

(1) pure random pick on an elem
(2) pick array[(N/2)]
(3) pick three elements randomly, and pick the median.

(2)&(3) at least help avoid the afore-mentioned infinite loop.

NOTE:  picking the median as pivot from the entire input ==> this is sometimes called median sort. obviously it's just a subset of quicksort

########################
####   complexity   ####
########################

## time

best case     O(n log n)
average case  O(n log n)
worst case    O(n^2)

## space

total     :  O(n)
auxiliary :  O(n)   // can be O(log n) if you implement without recursion

--------------------------

worst case is when your partition is always  1 | 2-to-N  ( or 1 to N-1 | N )
since you iterate N at every partition, the number of partitioning will be N in the worst case, hence O(n^2).

best case is the partitioning is almost always 50-50, thus binary split every time. depth will be logN, hense O(n log n)

average case is also O(n log n). for formal analysis using discrete probability, pls refer to the below wikipedia link

(ref)
http://en.wikipedia.org/wiki/Quicksort#Average-case_analysis_using_discrete_probability

but essentially, you can derive O(n log n) by simply preparing some sample input of N elements.
and try all the permutations of the N elements (= N! possible patterns)

space is mostly based on the depth of partitioning in this case, so its worst case is O(n), average is O(log n) when done without recusion (or using tail recursion aka tail call optimization).
the normal recursion causes each recursive call generates another stack frame space, which accumulates an overhead.

(ref)
http://stackoverflow.com/questions/12573330/why-does-quicksort-use-ologn-extra-space
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Quick/
http://en.wikipedia.org/wiki/Tail_call

################################
###    C++ implementation    ###
################################

(ref)
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88

------------------------------------
#include <iostream>
using namespace std;

void print(int arr[], int size)

for (int i = 0; i < size ; i++)
cout << arr[i] << ' ';
cout << endl;

int median(int x, int y, int z)

if((x >= y && y >= z) || (x <= y && y <= z)) return y;
else if((y >= x && x >= z) || (y <= x && x <= z)) return x;
else return z;

void quicksort(int a[], int left, int right)

if(right == left) return;
if(right == (left+1))
if (a[left] > a[right]){
swap(a[left],a[right]);
return;
}
int pivot = median(a[left],a[right],a[(left+right)/2]);
int i = left;
int k = right;

while(1)
{
while( a[i] < pivot ) i++;
while( a[k] > pivot ) k--;
if(i >= k) break;
swap(a[i],a[k]);
i++;k--;
}

if(left < i)  quicksort(a,left,i-1);
if(right > k) quicksort(a,k+1,right);

void swap(int& x, int& y)

x=x^y;
y=x^y;
x=x^y;

int main()

int input[] = {2,4,8,1,23,5,2,7,3,9};
//  int input[]={5,4,3,8,11};
int size = sizeof(input)/sizeof(int);
print(input, size);
quicksort(input,0,size-1);
print(input, size);

------------------------------------

1. 2014-05-27 23:17:01 |
2. Category : algo
3. Page View: