# Quicksort (Eiffel)

Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

A simple implementation of quicksort in Eiffel

## Overview

The core of the algorithm is recursive. After selecting a subarray to be sorted a pivot is chosen (either the middle element or at random) and all the elements of the list are sorted about the pivot. The subarrays of all the elements prior to the pivot and all the elements after the pivot are then sorted by the same scheme.

This implementation makes use of Eiffel's generics so that arrays of any type of comparable element can be sorted; and agents (first class functions) to allow for a choice of pivot selection functions.

## Core Algorithm

The core of the algorithm is implemented as a feature taking an array of generic elements, min and max elements defining the subarray to be sorted, and a function which takes two integers as argument and returns an integer. Elements are then moved to the front of the array if they are less than the original pivot element, and left where they are otherwise.

```<<quicksort subarray>>=
quicksort_subarray(a : ARRAY[X]; min, max : INTEGER; pivot_choice : FUNCTION[ANY, TUPLE[INTEGER, INTEGER], INTEGER]) is
local
pivot, i : INTEGER
do
if min < max then
pivot := pivot_choice.item([min, max])
a.swap(min, pivot); pivot := min
from
i := min + 1
until
i > max
loop
if a@i < a@min then
pivot := pivot + 1
a.swap(pivot, i)
end
i := i + 1
end
a.swap(min, pivot)
quicksort_subarray(a, min, pivot - 1, pivot_choice)
quicksort_subarray(a, pivot + 1, max, pivot_choice)
end
end -- quicksort_subarray
```

## Pivot Functions

The pivot functions are also implemented as simple features, either by selecting a random element of the array using the pseudorandom generator from the Eiffel library

```<<random pivot choice>>=
random : MIN_STAND
random_pivot(min, max : INTEGER) : INTEGER is
require
min < max
do
random.next
Result := random.last_integer(max - min) - 1 + min
ensure
(min <= Result) and (Result < max)
end
```

or by taking the middle element of the array

```<<middle pivot choice>>=
middle_pivot(min, max : INTEGER) : INTEGER is
require
min < max
do
Result := min + (max - min) #// 2
ensure
(min <= Result) and (Result < max)
end
```

## Public Feature

We can then provide two different versions of quicksort to export as public features, passing the different pivot choice functions in using Eiffel agents.

```<<public quicksort>>=
quicksort1(a: ARRAY[X]) is
require
a /= Void
do
quicksort_subarray(a, a.lower, a.upper, (agent random_pivot(?,?)))
ensure
a.count = old a.count
is_sorted(a)
end -- quicksort1
quicksort2(a: ARRAY[X]) is
require
a /= Void
do
quicksort_subarray(a, a.lower, a.upper, (agent middle_pivot(?,?)))
ensure
a.count = old a.count
is_sorted(a)
end -- quicksort2
```

## Correctness

Eiffel makes uses of Design by Contract to help ensure correctness. This takes the form of pre- and post-conditions for the features above. In the case of the exported quicksort features that includes the strong post-conditions that the array not have changed size, and that it actually be sorted. While these assertions can be turned off for speed, it is often useful to have them functioning as runtime checks. In this case that means we will have to provide a function to check whether the list is actually sorted or not.

```<<is sorted>>=
is_sorted(a: ARRAY[X]) : BOOLEAN is
require
a /= Void
local
i : INTEGER
do
Result := True
from
i := a.lower
invariant
a.valid_index(i)
until
i >= a.upper or not Result
loop
if not (a@i <= a@(i+1)) then
Result := False
end
i := i + 1
end
end -- is_sorted
```

## Quicksort Class

The features provided above must be placed into a suitably defined class. At the top of the class declaration we make the quicksort class generic, with the restriction that the parameter type must inherit from COMPARABLE, which ensures that the comparison operators used on the list elements will be well defined. We also hide the pivot choice functions, correctness checking, and core recursive algorithm from the public interface.

```<<quicksort.e>>=
class QUICKSORT[X -> COMPARABLE]
creation
make
feature {ANY}
make is
do
create random.make
end
public quicksort
feature {NONE}
random pivot choice
middle pivot choice
is sorted
quicksort subarray
end -- class QUICKSORT
```

## Testing

We can write a simple test class to actually see the quicksort procedure in action

```<<quicksort_test.e>>=
class QUICKSORT_TEST
creation
make
feature
make is
local
i : INTEGER
testarray_numeric : ARRAY[INTEGER_8]
testarray_string : ARRAY[STRING]
sorter_numeric : QUICKSORT[INTEGER_8]
sorter_string : QUICKSORT[STRING]
do
create sorter_numeric.make
create sorter_string.make
testarray_numeric := <<3,8,0,6,7,4,2,1,9,3,1,8,3,9,2,0,9,
4,6,3,0,5,7,9,3,2,5,7,9,0,1,9,3,1>>
sorter_numeric.quicksort1(testarray_numeric)
from
i := testarray_numeric.lower
until
i >= testarray_numeric.upper
loop
io.put_integer(testarray_numeric@i)
io.put_string(",")
i := i + 1
end
io.put_integer(testarray_numeric.last)
io.put_new_line
testarray_string := <<"Paris","London","Stockholm","Berlin","Oslo",
sorter_string.quicksort2(testarray_string)
from
i := testarray_string.lower
until
i >= testarray_string.upper
loop
io.put_string(testarray_string@i)
io.put_string(",")
i := i + 1
end
io.put_string(testarray_string.last)
io.put_new_line
end
end -- class QUICKSORT_TEST
```