|
||||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |
See:
Description
Interface Summary | |
SortObject | Algorithm interface for sorting a sequence according to a given comparator of elements. |
Class Summary | |
ArrayMergeSort | Performs a merge-sort in O(n log n) time, provided that the atRank(int) method of the Sequence works in O(1) time. |
ArrayQuickSort | Performs an in-place quicksort in expected O(n log n) time, provided that the atRank(int) method of the Sequence operates in O(1) time. |
HeapSort | Performs a heap-sort in O(n log n) time, provided only that the replaceElement(.) method of the Sequence works in O(1) time (and thus the style of implementation of the Sequence is not relevant). |
ListMergeSort | Performs a merge-sort in O(n log n) time, provided that isEmpty(), first(), insertLast(), and removeFirst() all operate in O(1) time. |
Package of sorting algorithms that operate on Sequences (defined
in jdsl.core.api). How to order the elements is defined
by implementations of jdsl.core.api.Comparator.
Each sorting algorithm class implements the SortObject
interface located in this package. Each algorithm modifies
directly the Sequence provided and leaves it in sorted order. The
sorts do not necessarily preserve the Position-element mappings of
the Sequence.
Some algorithm classes are optimized for particular Sequence
implementations. For example, sorting algorithms with the
Array prefix expect the atRank(.) method of
the provided Sequence to operate in constant time, and so
run optimally on array implementations. Algorithms with the
List prefix expect that insertions can be done in
constant time, and so run optimally on linked list
implementations. However, each algorithm will correctly sort any
Sequence.
Running times (time complexities) given for individual algorithms
depend on the assumption that the comparator can compare two
elements in constant time.
|
||||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |