Data Structures and Algorithms (H) Lecture 7 Notes

Sorting in Linear Time

CountingSort

To circumvent the bound of comparison sort, we need to get more information than mere comparisons. Since elements to be sorted are often numbers or strings, we can use this as a property that we could utilize.

Assume that the input elements are integers in . And for each element , CountingSort counts the number of elements less than . Then we reconstruct the array using this information. This will only use linear time. The CountingSort uses an array for counting and an array for writing the output.

Caution

If the input array contains duplicate elements, we must find a way to place them into different output positions.

The CountingSort proceeds as follows:

• Initialize the counter array
• Count elements
• Running sum elements
• Write elements to output

The runtime of CountingSort is straightforward to see: If then the runtime will be simply .

Correctness

• Loop invariant: At the start of each iteration of the last for loop, the elements are in the right position in and the last element in that has not yet been copied in , with value , belongs to .
• Initialization: At the start of the loop and no elements have been copied. The array provides for each element, the number of elements in that are smaller or equal to it. So the last element of , , naturally goes in position .
• Maintenance: At iteration , the loop invariant tells us that the element goes in and we copy in. Since the next element equal to in that has not yet been copied in should go in position , we decrement re-establishing the loop invariant.
• Termination: When the loop terminates . The loop invariant tells us that all the elements of are in the right position in thus there are no more elements to be copied.

Stability in Sorting

Definition: Stable Sorting

We say that a sorting algorithm is stable iff same elements appear in the output in the same order as they do in the input array.

The CountingSort is stable. This property is relevant when satellite data is attached to keys being sorted, e.g. sorting emails according to date.

Advantages & Disadvantages

Pros:

• Sorts in linear time integers in the range if .
• Is stable

Cons:

• Does not sort in place
• Can be slow if .

RadixSort

Since there are only 10 different integers in a digit of a decimal number (or the 52 possible letters in a English word), we can utilize the stability of CountingSort to limit the size of by sorting the digits: Example of running RadixSort:

The runtime of RadixSort is clearly

Correctness

The correctness of RadixSort follows from the stability of CountingSort and induction on columns.

• Loop Invariant: At each iteration of the for loop, the array is sorted on the last digits.
• Initialization: The array is trivially sorted on the empty set of digits for .
• Maintenance: The invariant tells us that the array is sorted on the last digits. Now we sorted the -th digit re-establishing the loop invariant, since our stable sort ensures that elements with same -th digit remain in the same order as before sorting.
• Termination: The loop terminates when . Then the loop invariant states that the array is completely sorted.