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. Tinkeringwith 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.
|method||statements||average time||worst-case time|
|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|