Bubble sort (Eiffel)

From LiteratePrograms

Other implementations: C | CLIPS | C++ | C# | Eiffel | Erlang | Io | Java | Lisp | Smalltalk

An implementation of bubble sort in Eiffel.

Contents 1 Overview 2 Bubble sort 3 Correctness 4 Class Declaration 5 Testing

Overview

Bubble sort works by repeatedly iterating through a container, swapping adjacent items when the first item is larger than the second. When no swapping is done, the container is sorted.

This implementation uses Eiffel generic facilities to enable sorting of arrays of elements of any type that inherits from COMPARABLE, providing flexibility while ensuring that comparison operators are meaningful.

Bubble sort

<<bubble_sort>>=
bubble_sort (a: ARRAY [X])
    require
        a_not_void: a /= Void
    local
        i, j: INTEGER
        temp: X
        done: BOOLEAN
    do
        from
            i := a.lower + 1
            done := False
        until
            i >= a.upper or done
        loop
            from
                j := a.lower
            until
                j >= a.upper
            loop
                if a [j] >= a [j + 1] then
                    temp := a [j]
                    a [j] := a [j + 1]
                    a [j + 1] := temp
                end
                j := j + 1
            end
            i := i + 1
        end
    ensure
        same_count: a.count = old a.count
        sorted: is_sorted (a, a.lower, a.upper)
    end

Correctness

Eiffel provides facility for Design by Contract, here taking the form of pre- and post-conditions requiring that the input array be non-empty, and ensuring that the resulting array have the same number of elements and be sorted. These contracts are converted into runtime checks after compilation for debugging, or can be turned off for finalized code. We do, however, require a definition of a routine to determine if the array is sorted:

<<is_sorted>>=
is_sorted (a: ARRAY[X]; min, max: INTEGER): BOOLEAN
    require
        a_not_void: a /= Void
        min_valid: a.valid_index (min)
        max_valid: a.valid_index (max)
    local
        i: INTEGER
    do
        Result := True
        from 
            i := min
        invariant
            a.valid_index (i)
        until
            i >= max or not Result
        loop
            Result := a [i] <= a [i + 1]
            i := i + 1
        end
    end

Class Declaration

As Eiffel is a fully object oriented language we must package these routines as features of a class

<<bubble_sort.e>>=
class BUBBLE_SORT [X -> COMPARABLE]
feature -- Sorting
    bubble_sort
feature -- Status report
    is_sorted
end

Testing

To test the BUBBLE_SORT class we can construct a simple test class demonstrating bubble sort running first over an array of integers, then over an array of strings.

<<bubble_sort_test.e>>=
class BUBBLE_SORT_TEST
create
    make
feature
    make is
        local
            i: INTEGER
            testarray_numeric: ARRAY [INTEGER_8]
            testarray_string: ARRAY [STRING]
            sorter_numeric: BUBBLE_SORT [INTEGER_8]
            sorter_string: BUBBLE_SORT [STRING]
        do
            create sorter_numeric
            create sorter_string
            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.bubble_sort (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 [i])
            io.put_new_line
            testarray_string := <<"Paris","London","Stockholm","Berlin","Oslo",
                                  "Rome","Madrid","Tallinn","Amsterdam","Dublin">>
            sorter_string.bubble_sort (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 [i])
            io.put_new_line
        end
end