Sortable Containers

Sortable Containers

Class `DS_SORTABLE`

Some containers such as priority queues or binary search trees keep their items sorted. On the other hand some other containers do not necessarily keep their items sorted but provide facilities to sort them on demand according to various comparison criteria and sorting algorithms. These latter containers inherit from the class DS_SORTABLE. One can sort the container with feature sort and inspect that the container is sorted with the boolean query sorted.

Class `DS_SORTER`

Because there are many ways to sort a container, the algorithm for sorting items and the comparison criterion are not part of the container implementation. They are instead part of a separate object called a sorter which is passed as argument to the routines sort and sorted from DS_SORTABLE. This allows the container to be sorted using different criteria. For example a list of persons can be sorted by name at some point in the execution of the program and later sorted by age. One would just have to use two different sorters when calling sort. These sorter objects are instances of class DS_SORTER. This class has two routines, sort and sorted, which are called by delegation from their counterparts in DS_SORTABLE. In addition to these two routines, DS_SORTER provides two other sets of routines: reverse_sort and reverse_sorted for sorting the items in the data structure in decreasing order, and sort_with_comparator and sorted_with_comparator for sorting the items using the comparison criterion provided by an instance of class DS_COMPARATOR. DS_SORTER is a deferred class, various sorting algorithms being implemented in its descendant classes.

Class `DS_COMPARATOR`

Class DS_COMPARATOR and its descendants provide sorters with a comparison criterion. The boolean query less_than compares two objects and returns true if the first one is considered smaller than the second one. This routine is deferred in DS_COMPARATOR but is given a concrete implementation in DS_COMPARABLE_COMPARATOR based on the fact that the objects involved in the comparison are of type COMPARABLE. It is easy to write other descendant classes of DS_COMPARATOR in order to customize the comparison criterion used in sorters.

When one wants to sort the items in a data structure in decreasing order, one can use DS_REVERSE_COMPARATOR in order to reverse the comparison criterion of a given comparator. The class DS_REVERSE_COMPARABLE_COMPARATORis also available as a shorthand when the objects to be compared are of type COMPARABLE.

Class `DS_INDEXABLE_SORTER`

Items stored in containers of type DS_INDEXABLE can be accessed by an integer index between 1 and count (the number of items in the container). This is an interesting property which is taken into account for the implementation of sorters for such containers. In addition to the sort and sorted routines inherited from DS_SORTER, class DS_INDEXABLE_SORTER also provides two new features for sorting the items stored within two given indexes in the container, subsort and subsorted. A call to sort (a_container) is therefore equivalent to subsort(a_container, 1,a_container.count). Similarly there are routines to sort ranges of items in reverse order or using a DS_COMPARATOR comparison criterion: reverse_subsort, reverse_subsorted, subsort_with_comparator and subsorted_with_comparator.

Routines sort, sorted, subsort and subsorted use comparator as their comparison criterion. This attribute is typically set by the creation procedure of the sorter in descendant classes of DS_INDEXABLE_SORTER. On the other hand reverse_sort, reverse_sorted, reverse_subsort and reverse_subsorted rely on the DS_REVERSE_COMPARATOR version of comparator.

Note that the implementation of the sorting algorithms in DS_INDEXABLE_SORTER and its descendant classes is of course heavily based on calls to item and put from DS_INDEXABLE. Therefore the use of these sorters will be optimal for containers whose implementation is based on arrays such as DS_ARRAYED_LIST for which item and put are efficient. However these two routines can be very time-consumming in containers implemented with linkable cells such as DS_LINKED_LIST and it is not recommended to use this kind of sorters in this case. If you need to sort a list, you are better off using an arrayed list rather than a linked list. New sorter classes with better algorithms to deal with linked containers will be provided in future releases.

Class `DS_BUBBLE_SORTER`

The class DS_BUBBLE_SORTER implements the bubble sort algorithm.

Class `DS_QUICK_SORTER`

The class DS_QUICK_SORTER implements the quick sort algorithm.

Class `DS_SHELL_SORTER`

The class DS_SHELL_SORTER implements the shell sort algorithm.

Class DS_SORTABLE

Class DS_SORTER

Class DS_COMPARATOR

Class DS_INDEXABLE_SORTER

Class DS_BUBBLE_SORTER

Class DS_QUICK_SORTER