Keep learning and keep sharing

Algorithm - quick sort

2016-02-05

The performance of quicksort

There are a lot of implementations of quick sort algorithm. Even though the time complexity of the algorithm is nlog(n), the real performance is highly depending on the partition algorithm.

The pseudo code of quicksort algorithm is as follows.

quickSort(A[], l, r)
      if l<r
      s <- partition (a, l, r)
      quickSort(A[], l, s-1)
      quickSort(A[], s+1, r)

Two partition algorithms

There are two famous partition algorithms. As my experience, Lumuto-Partition is better for performance and readibility.

Hoare-Partition algorithm

Hoare-Partition algorithm is not so good to understand due to several duplicated loops. The pseudo code of Hoare-partition algorithm:

partition(A[], l, r) 
    pivot <- A[l]  // select a value
    i = l-1, j = r + 1;
    loop true
        do  i++; while (A[i] < pivot);
        do  j--; while (A[j] > pivot);
        if  (i < j)
            swap(A[i], A[j])
        else
            return j // when i and j meets

Lumuto-Partition algorithm

The pseudo code of Lumuto-partition algorithm:

partition(A[], l, r) 
	pivot <- A[r]   // select value of the most right
	index <- l     // pointer the location to place the item smaller than pivot. The item will be placed by swap.
	for i <- low to high - 1 // loop
		if A[i] <= pivot      // when item is smaller than the pivot
			swap(A[i], A[index]) // swap with index
			index++ //move to the next
	swap(A[index], A[r]) // pivot value is located after the smaller values since the index++.
	return index // pivot index
1) 
     : 0 1 2 3 4 5
       - - - - - -
value: 1 4 5 2 7 3 
l: 0, r: 5, pivot value: 3, index: 0

2) 1 at 0 is smaller than 3. So swap and increase index. But index = 0 and i = 0 so no value change. 
index: 0, i = 0
-> index: 1, i = 1
     : 0 1 2 3 4 5
       - - - - - -
value: 1 4 5 2 7 3 

3) 4 at 1 is bigger than 3. No change
index: 1, i = 1
-> index: 1, i = 2
     : 0 1 2 3 4 5
       - - - - - -
value: 1 4 5 2 7 3 

4) 5 at 2 is bigger than 3. No change
index: 1, i = 2
-> index: 1, i = 3
     : 0 1 2 3 4 5
       - - - - - -
value: 1 4 5 2 7 3 

5) 2 at 3 is smaller than 3. So swap and increase index.
index: 1, i = 3
-> index: 2, i = 4
     : 0 1 2 3 4 5
       - - - - - -
value: 1 2 5 4 7 3 

5) 7 at 4 is bigger than 3. No change. Loop is finished.
index: 1, i = 4
-> index: 2, i = 5
     : 0 1 2 3 4 5
       - - - - - -
value: 1 2 5 4 7 3

6) Change the pivot item with the item the index
     : 0 1 2 3 4 5
       - - - - - -
value: 1 2 3 4 7 5

7) return index 2

The following source code presents the Lumuto-Partition implementation. This is very fast. Morover, the code is intuitive and easy to understand.

#include <stdio.h>

void swap(int array[], int a, int b){
	int tmp = array[a];
	array[a] = array[b];
	array[b] = tmp;
}

int partition(int array[], int low, int high){
	int last = array[high];
	int index = low;
	for (int i = low; i < high; i++){
		if (array[i] <= last){
			swap(array, i, index);
			index++;
		}
	}
	swap(array, index, high);
	return index;
}
/* quick sort function*/
void qsort(int array[], int low, int high){
	if (high <= low)
		return;
	int pivot = partition(array, low, high);
	qsort(array, low, pivot - 1);
	qsort(array, pivot + 1, high);
}
/* Test function*/
int main(){
	int sample[10] = { 3, 7, 8, 5, 2, 1, 9, 0, 4, 6 };
	qsort(sample, 0, 9);
	for (int i = 0; i <= 9; i++){
		printf("%d ", sample[i]);
	}
	return 0;
}

Similar Posts

Comments