Menu Introduction Bibliography

Basics Arrays Linked Lists Timing Estimates Summary

Sorting Insertion Sort Shell Sort Quick Sort Comparison External Sorts

Dictionaries Hash Tables Binary Trees Red-Black Trees Skip Lists Comparison

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. 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.