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