Next: 12. Graphs Up: 11. Sorting Algorithms Previous: 11.2 Counting Sort and Contents Index
Sorting is the fundamental algorithmic problem in computer science,
and it has a long history. Knuth [48] attributes the merge-sort
algorithm to von Neumann (1945). Quicksort is due to Hoare [39].
The original heap-sort algorithm is due to Williams [76], but the
version presented here (in which the heap is constructed bottom-up
in
time) is due to Floyd [28]. Lower-bounds for
comparison-based sorting appear to be folklore. The following table
summarizes the performance of these comparison-based algorithms:
| comparisons | in-place | |||||
| Merge-sort |
 |
worst-case | No | |||
| Quicksort |
 |
 |
expected | Yes | ||
| Heap-sort |
 |
 |
worst-case | Yes | ||
Each of these comparison-based algorithms has its advantages and disadvantages. Merge-sort does the fewest comparisons and does not rely on randomization. Unfortunately, it uses an auxilliary array during its merge phase. Allocating this array can be expensive and is a potential point of failure if memory is limited. Quicksort is an in-place algorithm and is a close second in terms of the number of comparisons, but is randomized, so this running time is not always guaranteed. Heap-sort does the most comparisons, but it is in-place and deterministic.
There is one setting in which merge-sort is a clear-winner; this occurs when sorting a linked-list. In this case, the auxiliary array is not needed; two sorted linked lists are very easily merged into a single sorted linked-list by pointer manipulations (see Exercise 11.2).
The counting-sort and radix-sort algorithms described here are due to Seward [66, Section 2.4.6]. However, variants of radix-sort have been used since the 1920s to sort punch cards using punched card sorting machines. These machines can sort a stack of cards into two piles based on the existence (or not) of a hole in a specific location on the card. Repeating this process for different hole locations gives an implementation of radix-sort.
Finally, we note that counting sort and radix-sort can be used to sort
other types of numbers besides non-negative integers. Straightforward
modifications of counting sort can sort integers, in any interval
, in
time. Similarly, radix sort can sort
integers in the same interval in
time. Finally, both of these
algorithms can also be used to sort floating point numbers in the IEEE 754
floating point format. This is because the IEEE format is designed to
allow the comparison of two floating point numbers by comparing their values
as if they were integers in a signed-magnitude binary representation
[2].
. Give a sample illustration of one possible
execution of quicksort on the same array.
always use
![$ \ensuremath{\ensuremath{\mathit{a}}[\ensuremath{\mathit{i}}]}$](img4488.png){kind=small}
as a pivot. Give an example of an input array of length
in which
such an implementation would perform
comparisons.
always use
![$ \ensuremath{\ensuremath{\mathit{a}}[\ensuremath{\mathit{i}}+\ensuremath{\mathit{n}}/2]}$](img4492.png){kind=small}
as a pivot. Given an example of an input array of length
in which
such an implementation would perform
comparisons.
that chooses a pivot deterministically, without first looking at
any values in
![$ \ensuremath{\ensuremath{\ensuremath{\mathit{a}}[\ensuremath{\mathit{i}}]}},\ld...
...th{\ensuremath{\mathit{a}}[\ensuremath{\mathit{i}}+\ensuremath{\mathit{n}}-1]}}$](img4496.png){kind=small}
, there exists an input array of length
that causes this implementation to perform
comparisons.
, that you could pass as an argument
to
and that would cause quicksort to perform
comparisons. (Hint: Your comparator does not actually
need to look at the values being compared.)
.
comparisons. Justify your answer.
that are not correctly
sorted by the comparison tree in Figure 11.6.
.
leaves has height at least 
.
leaves, then the expected height of this leaf is at least 
.
given here works when the input
array,
contains only
integers.