deferred class ABSTRACT_SORTER [X]

Features exported to ANY

Some algorithms to sort any COLLECTION, using a given order relation in deferred methods lt, gt, lte and gte.

Elements are sorted using increasing order: small elements at the beginning of the collection, large at the end (decreasing order is implemented by class REVERSE_COLLECTION_SORTER). Note that "small" means "a is smaller than b" when "lt (a, b)", no matter what lt is.

Direct parents

non-conformant parents

ANY

Known children

conformant children

COLLECTION_SORTER, COMPARATOR_COLLECTION_SORTER, REVERSE_COLLECTION_SORTER

Summary

exported features

Details

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

  • 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)