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

method statements average time worst-case time

insertion sort 9 O (n 2) O (n 2)

shell sort 17 O (n 1.25) O (n 1.5)

quicksort 21 O (n lg n ) O (n 2)

Table 2-2: Comparison of Methods

count insertion shell quicksort

16 39 ms 45 ms 51 ms

256 4,969 ms 1,230 ms 911 ms

4,096 1.315 sec .033 sec .020 sec

65,536 416.437 sec 1.254 sec .461 sec