quicksort

Introduction

This program implements the quicksort algorithm for integers. It demonstrates recursion, allocating sequences, iterating over sequences, and concatenating sequences.

Quicksort is a divide and conquer algorithm, meaning it recursively partitions the problem into smaller problems until they are trivially solved. The trivially solved case is them empty sequence, which is sorted. To sort a non-empty sequence, quicksort selects one element of the sequence as a pivot. It then partitions the sequence into three new sequences: a left sequence containing all items from the original sequence that are smaller than the pivot, a right sequence containing all items that are larger, and a center sequence containing all items that are equal to the pivot. The left and right sequences are guaranteed to be smaller than the original sequence. The center sequence is guaranteed to be sorted.

After the partitioning, the sorted sequence is obtained by sorting the left sequence, sorting the right sequence, and then concatenating the three sorting sequences in the order left, center, right. The resulting sequence is returned.

C

In C, the implementation looks as follows:

#include <stdio.h>

int *quicksort(int *items, int size) {
	int left[size], center[size], right[size];
	int i, n, pivot, left_size = 0, center_size = 0, right_size = 0;

	if(size <= 0 || !items) return NULL;

	pivot = items[0];
	for(i = 0; i < size; i++) {
		n = items[i];
		if(n < pivot) left[left_size++] = n;
		else if(pivot < n) right[right_size++] = n;
		else center[center_size++] = n;
	}

	quicksort(left, left_size);
	quicksort(right, right_size);

	memcpy(items, left, left_size * sizeof(int));
	memcpy(items + left_size, center, center_size * sizeof(int));
	memcpy(items + left_size + center_size, right,
		right_size * sizeof(int));

	return items;
} 

int main(int argc, char **argv) {
	int i;
#define SIZE 5
	int items[SIZE] = { 1, 3, 5, 4, 2 };

	quicksort(items, SIZE);

	for(i = 0; i < SIZE; i++) printf("%d\n", items[i]);

	return 0;
}

A peculiarity of this implementation is that the quicksort function takes a size parameter, in addition to the array that is to be sorted. This is necessary, because C only stores the element of arrays, not their sizes. Since we need to know how many elements are in the array, we must pass this in as an extra parameter.

The space for left, center, and right is allocated on the stack, which means that it will be de-allocated automagically when quicksort returns. To make sure there is enough space in each of them, they are all made equally large as items. This wastes quite some space. Perhaps a better solution would be to use dynamic memory allocation, but that is somewhat cumbersome in C.

In the last step before returning, quicksort overwrites items with the sorted values. This side effect may be undesired in many situations; in such cases, the items to be sorted should be copied into a newly allocated array before calling quicksort.

This implementation contains 127 words.

OCaml

In OCaml, the quicksort algorithm can be implemented like this:

open Printf

let rec quicksort items =
	match items with
		  [] -> []
		| x::xs -> quicksort_rec xs x [] [x] []
and quicksort_rec items pivot left center right =
	match items with
		  [] -> (quicksort left) @ center @
			(quicksort right)
		| x::xs ->
			if x < pivot then
				quicksort_rec xs pivot
					(x::left) center right
			else if pivot < x then
				quicksort_rec xs pivot left
					center (x::right)
			else quicksort_rec xs pivot left
				(x::center) right

let _ = List.iter (printf "%d\n") (quicksort [1; 3; 5; 4; 2])

This implementation demonstrates several features of OCaml. First of all, pattern matching.

match items with
	  [] -> …
	| x::xs -> …

first compares items to [] (the empty list). If this results in a match, the first … is evaluated and returned. Otherwise, matching continues with the clause after the next |, which is x::xs. This uses list construction syntax (x::xs returns the list resulting from prepending the element x to the list xs) to match a list with at least one element (xs could match the empty list). It evaluates the … after the arrow with x bound to the first element of the list and xs bound to the rest of the list.

Secondly, mutually recursive functions. OCaml normally requires that bindings be defined before they are used. This poses a problem for quicksort and quicksort_rec, because they call one another, and thus would both have to be defined first. The let rec … and … takes care of this, by allowing all defined bindings to see one another. More bindings can be defined by adding more and clauses.

Finally, note that (printf "%d\n") calls printf with one argument fewer than it requires. This is called currying (after Haskell Curry). The result is a new function, which will complete the specified function call once the remaining arguments are supplied. Thus, (printf "%d\n") returns a function that takes an integer argument and prints it, followed by a newline.

This version has 87 words.

Ruby

The following implements quicksort in Ruby:

def quicksort items
	return items if items.empty?
	left = []
	center = []
	right = []
	pivot = items[0]
	items.each do |item|
		if item < pivot
			left << item
		elsif pivot < item
			right << item
		else
			center << item
		end
	end
	quicksort(left) + center + quicksort(right)
end

puts quicksort([1,3,5,4,2])

Again, we see the each method in conjunction with a block to iterate over items. We see the infix operator << to append an item to an array, and the + operator for concatenating arrays.

The program consists of 50 words.

Common Lisp

For Common Lisp, we have the following implementation:

(defun quicksort (items)
	(if (null items) items
		(loop for x in items
			with pivot = (car items)
			with left = '()
			with center = '()
			with right = '()
			do (cond
				((< x pivot) (push x left))
				((< pivot x) (push x right))
				(t (push x center)))
			finally (return (nconc
					(quicksort left) center
					(quicksort right))))))
	
(format t "~{~A~%~}" (quicksort '(1 3 5 4 2)))

Again, we see the Loop Facility being used. A few other noteworthy things: (null list) tests if list is the empty list. (push item list) prepends item to the list stored in list, and stores the updated list in the same place. (nconc …) concatenates the lists it is passed and returns the result. Both of these are destructive, meaning they modify their arguments.

(cond …) takes a number of clauses of the form (test expr …). It evaluates each test in order until one test passes, then evaluates the expr … for that clause, returning the result of the last expr evaluated. If no test passed, cond returns nil. t is Common Lisp's true value, which means the last clause in this cond form will be executed if none of the others are.

This program also sports an interesting format string: "~{~A~%~}". The ~{ takes the next argument to format, which must be a list, and applies everything between ~{ and ~} to each element of that list. In this case, the elements of the list are printed (aestetically), with a newline after each one.

The program contains 64 words.