expanded class COLLECTION_SORTER [X -> COMPARABLE]

All features

Some algorithms to sort any COLLECTION[COMPARABLE].

Elements are sorted using increasing order: large elements at the beginning of the collection, small at the end (increasing order is implemented by class COLLECTION_SORTER).

How to use this expanded class :

         local
            sorter: COLLECTION_SORTER[INTEGER]
            array: ARRAY[INTEGER]
         do
            array := <<1,3,2>>
            sorter.sort(array)
            check
               sorter.is_sorted(array)
            end
            ...

Direct parents

conformant parents

ABSTRACT_SORTER

Summary

exported features

Auxiliary functions

Details

lt (x: X, y: X): BOOLEAN
gt (x: X, y: X): BOOLEAN
lte (x: X, y: X): BOOLEAN
gte (x: X, y: X): BOOLEAN
is_sorted (c: COLLECTION[X]): BOOLEAN

Is c already sorted ? Uses lte for comparison.

require

  • c /= Void

ensure

  • c.is_equal(old c.twin)

has (c: COLLECTION[X], element: X): BOOLEAN

require

  • c /= Void
  • is_sorted(c)

ensure

  • Result = c.has(element)

index_of (c: COLLECTION[X], element: X): INTEGER

require

  • c /= Void
  • is_sorted(c)

ensure

  • not c.is_empty implies c.valid_index(Result)
  • c.has(element) implies c.item(Result).is_equal(element)

add (c: COLLECTION[X], element: X)

Add element in collection c keeping the sorted property.

require

  • c /= Void
  • is_sorted(c)

ensure

  • c.count = old c.count + 1
  • is_sorted(c)

insert_index (c: COLLECTION[X], element: X): INTEGER

retrieve the upper index for wich gt

require

  • c /= Void
  • is_sorted(c)

ensure

  • c.valid_index(Result) implies gt(c.item(Result), element)
  • c.valid_index(Result - 1) implies lte(c.item(Result - 1), element)
  • Result.in_range(c.lower, c.upper + 1)

sort (c: COLLECTION[X])

Sort c using the default most efficient sorting algorithm already implemented.

require

  • c /= Void

ensure

  • c.count = old c.count
  • is_sorted(c)

quick_sort (c: COLLECTION[X])

Sort c using the quick sort algorithm.

require

  • c /= Void

ensure

  • c.count = old c.count
  • is_sorted(c)

von_neuman_sort (c: COLLECTION[X])

Sort c using the Von Neuman algorithm. This algorithm needs to create a second collection. Uses infix "lte" for comparison.

require

  • c /= Void

ensure

  • c.count = old c.count
  • is_sorted(c)

heap_sort (c: COLLECTION[X])

Sort c using the heap sort algorithm.

require

  • c /= Void

ensure

  • c.count = old c.count
  • is_sorted(c)

bubble_sort (c: COLLECTION[X])

Sort c using the bubble sort algorithm. Uses infix "<" for comparison.

require

  • c /= Void

ensure

  • c.count = old c.count
  • is_sorted(c)

von_neuman_line (src: COLLECTION[X], dest: COLLECTION[X], count: INTEGER, d_count: INTEGER, lower: INTEGER, imax: INTEGER)

require

  • src /= dest
  • src.lower = dest.lower
  • src.upper = dest.upper
  • count >= 1
  • d_count = count * 2
  • lower = src.lower
  • imax = src.upper + 1

ensure

  • d_count >= dest.count implies is_sorted(dest)

von_neuman_inner_sort (src: COLLECTION[X], dest: COLLECTION[X], sg1: INTEGER, count: INTEGER, imax: INTEGER)

require

  • src.valid_index(sg1)

heap_repair (c: COLLECTION[X], c_lower: INTEGER, first: INTEGER, last: INTEGER)

Repair the heap from the node number first It considers that the last item of c is number last It supposes that children are heaps.

require

  • c /= Void
  • c.lower = c_lower
  • c_lower <= first
  • last <= c.upper

quick_sort_region (c: COLLECTION[X], left: INTEGER, right: INTEGER)