This is the first post in my quest to be a better programmer. Quicksort is one of the ‘standard’ sorting algorithms. Its fairly easy to implement, and normally runs fairly quickly. I’ve implemented quicksort in both C and Scheme, although I think my Scheme implementation is more of a pseudo-quicksort due to a reluctance to break from the functional style encouraged by Scheme syntax.

Quicksort Overview

The ‘Partition’ algorithm is at the core of a quicksort implementation, and this partitions an array into groups of ‘less than x’ and ‘more than x’, with x itself being placed inbetween. The final position of x is the value returned by the partition function. In my simple implementation, the choice of x remains constant (either the first or last element). Randomizing this is the main way to increase the worst case speed of this algorithm.

After partitioning the initial input, quicksort recursivly calls itself on the ‘less-than’ and ‘more-than’ groups returned from partition. The result is a chain of recursive calls which continues until quicksort is trying to sort a single number.

Check out Wikipedia to get a more in-depth understanding of quicksort.

Special Property

Quicksort is good because it sorts ‘in-place’. In other words it doesn’t use a secondary array to sort the elements into. This can save a lot of memory, especially if you are sorting a list of complicated data structures which are a few KB each.

My C Implementation

void Quicksort(int A[], int p, int r){
	
	if(p<r){
		int q = Partition(A, p, r);
		Quicksort(A, p, q-1);
		Quicksort(A, q+1, r);
	}
}

int Partition(int A[], int p, int r){
	int j, temp;
	
	int x = A[r];
	int i = p -1;
	
	for(j = p;j<r;j++){
		if(A[j]<= x)
		{
			i++;
			temp = A[i];
			A[i] = A[j];
			A[j] = temp;
		}
	}
	temp = A[r];
	A[r] = A[i +1];
	A[i+1] = temp;
	
	return i+1;

My Scheme Implementation

I think its worth noting that the scheme implementation doesn’t exactly sort ‘in-place’. Instead it recursivly builds up secondary lists then joins them together at the end as the return value instead of moving the elements around in a single list. However the amount of memory used should still be in the order of the number of elements in the input array unlike other sorting algorithms (counting-sort, and bucket-sort come to mind) which use secondary arrays which do not form part of the solution.

(define pHelper (lambda (all chk l m)
                  (cond ((null? all) (cons l (cons chk (cons m '()))))
                        (else
                        (let ((x (car all)))
                          (if (<= x chk) 
                              (pHelper (cdr all) chk (cons x l) m)
                              (pHelper (cdr all) chk l (cons x m))))))))

(define partition (lambda (l)
                      (pHelper (cdr l) (car l) '() '())))



(define quicksort (lambda (l)
                    (cond ((null? l) l)
                          (else
                          (let ((lx (partition l)))
                            (append (quicksort (car lx)) (cons (cadr lx) (quicksort (caddr lx)))))))))

Further Reading

If you're looking to learn more about basic CS algorithms like Quicksort, I suggest checking out the book Introduction to Algorithms on Amazon