0.6 Sorting  (Page 2/20)

When equal elements are indistinguishable, such as with integers, or more generally, any data where the entire element is the key, stability is not an issue. However, assume that the following pairs of numbers are to be sorted by their first coordinate:

(4, 1) (3, 7) (3, 1) (5, 6)

In this case, two different results are possible, one which maintains the relative order of records with equal keys, and one which does not:

(3, 7) (3, 1) (4, 1) (5, 6) (order maintained)

(3, 1) (3, 7) (4, 1) (5, 6) (order changed)

Unstable sorting algorithms may change the relative order of records with equal keys, but stable sorting algorithms never do so. Unstable sorting algorithms can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, so that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original data order as a tie-breaker. Remembering this order, however, often involves an additional space cost.

Sorting based on a primary, secondary, tertiary, etc. sort key can be done by any sorting method, taking all sort keys into account in comparisons (in other words, using a single composite sort key). If a sorting method is stable, it is also possible to sort multiple times, each time with one sort key. In that case the sort keys can be applied in any order, where some key orders may lead to a smaller running time.

6.1.1. insertion sort

(From Wikipedia, the free encyclopedia)

Insertion sort is a simple sorting algorithm , a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort , heapsort , or merge sort , but it has various advantages:

• Simple to implement
• Efficient on (quite) small data sets
• Efficient on data sets which are already substantially sorted: it runs in O(n + d) time, where d is the number of inversions
• More efficient in practice than most other simple O (n2) algorithms such as selection sort or bubble sort : the average time is n2/4 and it is linear in the best case
• Stable (does not change the relative order of elements with equal keys)
• In-place (only requires a constant amount O(1) of extra memory space)
• It is an online algorithm , in that it can sort a list as it receives it.

Algorithm

In abstract terms, every iteration of an insertion sort removes an element from the input data, inserting it at the correct position in the already sorted list, until no elements are left in the input. The choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm.

Sorting is typically done in-place. The resulting array after k iterations contains the first k entries of the input array and is sorted. In each step, the first remaining entry of the input is removed, inserted into the result at the right position, thus extending the result:

becomes:

with each element>x copied to the right as it is compared against x.

The most common variant, which operates on arrays, can be described as: