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
- Simplicity. The number of statements required for each
algorithm may be found in
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
|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 |