Comparison of Sorting

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.



 

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(n7/6) O(n4/3)
quicksort 21 O(nlgn) O(n2)

 

Table 2-3: Sort Timings
count insertion shell quicksort
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

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>