Comparison
In this section we will compare the sorting algorithms covered:
insertion sort, shell sort, and quicksort. There are several
factors that influence the choice of a sorting algorithm:
- Stable sort. Recall that a stable sort will leave identical
keys in the same relative position in the sorted output.
Insertion sort is the only algorithm covered that is stable.
- Space. An in-place sort does not require any extra space to
accomplish its task. Both insertion sort and shell sort are in-
place sorts. Quicksort requires stack space for recursion, and
therefore is not an in-place sort. Tinkering with the algorithm
considerably reduced the amount of time required.
- Time. The time required to sort a dataset
can easily become astronomical (Table 1-1).
Table 2-2 shows the relative timings for each method.
The time required to sort a randomly ordered dataset is shown in
Table 2-3.
- Simplicity. The number of statements required for each
algorithm may be found in
Table 2-2.
Simpler algorithms result in fewer programming errors.
Table 2-2: Comparison of Sorting Methods
method | statements | average time | worst-case time |
insertion sort | 9 | O(n2) | O(n2) |
shell sort | 17 | O(n1.25) | O(n1.5) |
quicksort | 21 | O(n lg n) | O(n2) |
Table 2-3: Sort Timings
count | insertion | shell | quicksort |
16 | 39 µs | 45 µs | 51 µs |
256 | 4,969 µs | 1,230 µs | 911 µs |
4,096 | 1.315 sec | .033 sec | .020 sec |
65,536 | 416.437 sec | 1.254 sec | .461 sec |