quicksort

# quicksort

2006-09-19

## 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.