Clean Code hochulshin.com

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)
      p <- A[l]
      i <-l, j<- r
      while i <= j
	 while A[i] <= p: i++
	 while A[j] >= p: j--
	 if i<j : swap(A[i], A[j])
      swap(A[l], A[j])
      return j

Lumuto-Partition algorithm

The pseudo code of Lumuto-partition algorithm:

partition(A[], l, r)
      x <- A[r]
      i <- l - 1
      for j in l->r-1
      	if A[j] <= x
      	   i++, swap(A[i], A[j])
      swap(A[i+1], A[r])
      return i + 1

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;
}

Comments