Quicksort (Eiffel)

From LiteratePrograms

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

Contents 1 Overview 2 Core Algorithm 3 Pivot Functions 4 Public Feature 5 Correctness 6 Quicksort Class 7 Testing

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",
                                  "Rome","Madrid","Tallinn","Amsterdam","Dublin">>
            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

Download code