+
Point of view
All features
expanded class COLLECTION_SORTER [X_ -> COMPARABLE]
Summary
top
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
Insert list: ABSTRACT_SORTER
Overview
top
Features
{}
Auxiliary functions
{}
{ANY}
  • is_sorted (c: COLLECTION[X_]): BOOLEAN
    Is c already sorted ? Uses lte for comparison.
  • has (c: COLLECTION[X_], element: X_): BOOLEAN
  • index_of (c: COLLECTION[X_], element: X_): INTEGER_32
  • add (c: COLLECTION[X_], element: X_)
    Add element in collection c keeping the sorted property.
  • insert_index (c: COLLECTION[X_], element: X_): INTEGER_32
    retrieve the upper index for which gt
  • sort (c: COLLECTION[X_])
    Sort c using the default most efficient sorting algorithm already implemented.
  • quick_sort (c: COLLECTION[X_])
    Sort c using the quick sort algorithm.
  • von_neuman_sort (c: COLLECTION[X_])
    Sort c using the Von Neuman algorithm.
  • heap_sort (c: COLLECTION[X_])
    Sort c using the heap sort algorithm.
  • bubble_sort (c: COLLECTION[X_])
    Sort c using the bubble sort algorithm.
{}
lt (x: X_, y: X_): BOOLEAN
effective function
{}
top
gt (x: X_, y: X_): BOOLEAN
effective function
{}
top
lte (x: X_, y: X_): BOOLEAN
effective function
{}
top
gte (x: X_, y: X_): BOOLEAN
effective function
{}
top
is_sorted (c: COLLECTION[X_]): BOOLEAN
effective function
{ANY}
top
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
effective function
{ANY}
top
require ensure
  • Result = c.has(element)
index_of (c: COLLECTION[X_], element: X_): INTEGER_32
effective function
{ANY}
top
require 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_)
effective procedure
{ANY}
top
Add element in collection c keeping the sorted property.
require ensure
insert_index (c: COLLECTION[X_], element: X_): INTEGER_32
effective function
{ANY}
top
retrieve the upper index for which gt
require 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_])
effective procedure
{ANY}
top
Sort c using the default most efficient sorting algorithm already implemented.
require
  • c /= Void
ensure
quick_sort (c: COLLECTION[X_])
effective procedure
{ANY}
top
Sort c using the quick sort algorithm.
require
  • c /= Void
ensure
von_neuman_sort (c: COLLECTION[X_])
effective procedure
{ANY}
top
Sort c using the Von Neuman algorithm.
This algorithm needs to create a second collection. Uses infix "lte" for comparison.
require
  • c /= Void
ensure
heap_sort (c: COLLECTION[X_])
effective procedure
{ANY}
top
Sort c using the heap sort algorithm.
require
  • c /= Void
ensure
bubble_sort (c: COLLECTION[X_])
effective procedure
{ANY}
top
Sort c using the bubble sort algorithm.
Uses infix "<" for comparison.
require
  • c /= Void
ensure
von_neuman_line (src: COLLECTION[X_], dest: COLLECTION[X_], count: INTEGER_32, d_count: INTEGER_32, lower: INTEGER_32, imax: INTEGER_32)
effective procedure
{}
top
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_32, count: INTEGER_32, imax: INTEGER_32)
effective procedure
{}
top
require
  • src.valid_index(sg1)
heap_repair (c: COLLECTION[X_], c_lower: INTEGER_32, first: INTEGER_32, last: INTEGER_32)
effective procedure
{}
top
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_32, right: INTEGER_32)
effective procedure
{}
top