Package jdsl.core.algo.sorts

Package of sorting algorithms that operate on Sequences (defined in jdsl.core.api).

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.
ListQuickSort Performs an in-place quicksort in expected O(n log n) time, provided that the first(), last(), after(), and before() methods of the Sequence work in O(1) time.
 

Package jdsl.core.algo.sorts Description

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.