In this section we will compare the sorting algorithms covered:
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
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
||O(n lg n)
Table 2-3: Sort Timings