1.124 Lecture 9 - Sorting Algorithms

• Performance Criteria
• Selection sort
• Insertion sort
• Shell sort
• Quicksort
• Choosing a sorting algorithm

Sorting

Performance criteria

• Running time: Typically, an elementary sorting algorithm requires O(N^2) steps to sort N randomly arranged items. More sophisticated sorting algorithms require O(N log N) steps on average. Algorithms differ in the constant that appears in front of the N^2 or N log N. Furthermore, some sorting algorithms are more sensitive to the nature of the input than others. Quicksort, for example, requires O(N log N) time in the average case, but requires O(N^2) time in the worst case.
• Memory requirements: The amount of extra memory required by a sorting algorithm is also an important consideration. In place sorting algorithms are the most memory efficient since they require practically no additional memory.  Linked list representations require an additional N words of memory for a list of pointers. Still other algorithms require sufficent memory for another copy of the input array. These are the most inefficient in terms of memory usage.
• Stability. This is the ability of a sorting algorithm to preserve the relative order of equal keys in a file.

 In the algorithms given below, we assume that the array to be sorted is stored in the memory locations a[1],a[2],...,a[N]. The memory location a[0] is reserved for special keys called sentinels which are described below.

Selection sort

Approach:
 

• Find the smallest element in the array and exchange it with the element in the first position.
• Find the second smallest element in the array and exchange it with the element in the second position.
• Continue this process until done.

selection.C

inline void swap(ItemType a[], int i, int j)
  {
  ItemType t = a[i];
  a[i] = a[j];
  a[j] = t;
  }

void selection(ItemType a[], int N)
  {
  int i, j, min;
 
  for (i = 1; i < N; i++)
      {
      min = i;
      for (j = i+1; j <= N; j++)
        if (a[j] < a[min]) min = j;
      swap(a,min,i);
      }
  }
 

Selection sort is easy to implement; there is little that can go wrong with it. However, the method requires O(N^2) comparisons and so it should only be used on small files. There is an important exception to this rule. When sorting files with large records and small keys, the cost of exchanging records controls the running time. In such cases, selection sort requires O(N) time since the number of exchanges is at most N.

Insertion sort

 Approach:
 
 

• Choose the second element in the array and place it in order with respect to the first element.
• Choose the third element in the array and place it in order with respect to the first two elements.
• Continue this process until done.

Here is the code for insertion sort:

insertion.C

void insertion(ItemType a[], int N)
  {
  int i, j;
  ItemType v;
 
  for (i = 2; i <= N; i++)
      {
      v = a[i];
      j = i;
      while (a[j-1] > v)
         {
          a[j] = a[j-1];
          j--;
         }
      a[j] = v;
      }
  }

 It is important to note that there is no test in the while loop to prevent the index j from running out of bounds. This could happen if v is smaller than a[1],a[2],...,a[i-1]. To remedy this situation, we place a  sentinel key in a[0], making it at least as small as the smallest element in the array. The use of a sentinel is more efficient than performing a test of the form:

while (j > 1 && a[j-1] > v)

Insertion sort is an O(N^2) method both in the average case and in the worst case. For this reason, it is most effectively used on files with roughly N < 20.  However, in the special case of an almost sorted file, insertion sort requires only  linear time.

 Shell sort

Definition: An  h-sorted  file is one which has the property that taking every h th element (starting anywhere) yields a sorted file.

Approach:
 

• Choose an initial large step size, h_K, and use insertion sort to produce an h_K-sorted file.
• Choose a smaller step size, h_{K-1}, and use insertion sort to produce an h_{K-1}-sorted file, using the h_K-sorted file as input.
• Continue this process until done.

 

Each stage in the sorting process brings the elements closer to their final positions. The method derives its efficiency from the fact that insertion sort is able to exploit the order present in a partially sorted input file; input files with more order to them require a smaller number of exchanges.

It is important to choose a good sequence of increments. A commonly used sequence is {(3^K-1)/2, . . . 121, 40, 13, 4, 1}, which is obtained from the recurrence h_k = 3 h_{k+1}+1. Note that the sequence obtained by taking powers of 2 leads to bad performance because elements in odd positions are not compared with elements in even positions until the end.

Here is the complete code for shell sort:

shell.C

void shellsort(ItemType a[], int N)
  {
  int i, j, h;
  ItemType v;
 
  for (h = 1; h <= N/9; h = 3*h+1);
 
  for (; h > 0; h /= 3)
    for (i = h+1; i <= N; i++)
 {
 v = a[i];
 j = i;
 while (j > h && a[j-h] > v)
     {
     a[j] = a[j-h];
     j -= h;
     }
 a[j] = v;
 }
  }
 

Shell sort requires O(N^{3/2}) operations in the worst case, which means that it can be quite effectively used even for moderately large files (say N < 5000).

Quicksort

Since the algorithm is based on recursion, we assume that the array (or subarray) to be sorted is stored in the memory locations  a[l],a[l+1], . . . ,a[r].  In order to sort the full array, we simply initialize the algorithm with  l = 1 and  r = N.

Approach:

•  Partition the subarray  a[l],a[l+1],. . . ,a[r] into two parts, such that
•  element  a[i] is in its final place in the array for some  i in [l,r] .
•  none of the elements in a[l],a[l+1],. . . a[i-1] are greater than  a[i].
•  none of the elements in  a[i+1],a[i+2],. . . ,a[r] are less than  a[i].
•  Recursively partition the two subarrays,  a[l],a[l+1],. . . ,a[i-1]} and a[i+1],a[i+2],. . . ,a[r], until the entire array is sorted.

 

•  Choose a[r] to be the element that will go into its final position.
• item Scan from the left end of the subarray until an element greater than a[r] is found.
•  Scan from the right end of the subarray until an element less than a[r] is found.
•  Exchange the two elements which stopped the scans.
• Continue the scans in this way. Thus, all the elements to the  left of the left scan pointer will be less than  a[r] and all the elements to the right of the right scan pointer will be greater than  a[r].
•  When the scan pointers cross we will have two new subarrays, one with elements less than  a[r] and the other with elements greater than a[r]. We may now put  a[r] in its final place by exchanging it with the leftmost element in the right subarray.

quicksort.C

void quicksort(ItemType a[], int l, int r)
  {
  int i, j;
  ItemType v;

  if (r > l)
      {
      v = a[r];
      i = l - 1;
      j = r;
      for (;;)
   {
   while (a[++i] < v);
   while (a[--j] > v);
   if (i >= j) break;
   swap(a,i,j);
   }
      swap(a,i,r);
      quicksort(a,l,i-1);
      quicksort(a,i+1,r);
      }
  }

Note that this code requires a sentinel key in  a[0] to stop the right-to-left scan in case the partitioning element is the smallest element in the file. Quicksort requires O(N log N)  operations in the average case. However, its worst case performance is O(N^2), which occurs in the case of an already sorted file!

There are a number of improvements which can be made to the basic quicksort algorithm.
 

•  Using the median of three partitioning method makes the worst case far less probable, and it eliminates the need for sentinels. The basic idea is as follows.
• Choose three elements, a[l],  a[m] and  a[r], from the left, middle and right of the array. Sort them (by direct comparison) so that the median of the three is in a[m] and the largest is in  a[r]. Now exchange  a[m] with  a[r-1]. Finally, we run the partitioning algorithm on the subarray  a[l+1],a[l+2], . . . ,a[r-2] with  a[r-1] as the partitioning element.
• Another improvement is to remove recursion from the algorithm by using an explicit stack. The basic idea is as follows.
• After partitioning, push the larger subfile onto the stack. The smaller subfile is processed immediately by simply resetting the parameters l and r  (this is known as  end-recursion removal). With the explicit stack implementation, the maximum stack size is about log_2 N. On the other hand, with the recursive implementation, the underlying stack could be as large as N.
•  A third improvement is to use a cutoff to insertion sort whenever small subarrays are encountered. This is because insertion sort, albeit an O(N^2) algorithm, has a sufficiently small constant in front of the N^2 to be more efficient than quicksort for small N. A suitable value for the cutoff subarray size would be approximately in the range 5  ~ 25.

Choosing a Sorting Algorithm

Bubble sort, which is included in Table 1 for comparison purposes only, is generally best avoided.
Insertion sort requires linear time for {\em almost sorted} files, while selection sort requires linear time for files with large records and small keys.

Insertion sort and selection sort should otherwise be limited to small files.

Quicksort is the method to use for very large sorting problems. However, its performance may be significantly affected by subtle implementation errors. Furthermore, quicksort performs badly if the file is already sorted.

Another possible disadvantage is that quicksort is not stable i.e.~it does not preserve the relative order of equal keys. All of the above sorting algorithms are in-place methods. Quicksort requires a small amount of additional memory for the auxiliary stack.

There are a few other sorting methods which we have not considered. Heapsort requires
O(N log N) steps both in the average case and the worst case, but it is about twice as slow as quicksort on average.

Mergesort another O(N log N) algorithm in the average and worst cases. Mergesort is the method of choice for sorting  linked lists, where sequential access is required.
 
 

Number of Comparisons

Number of Exchanges

 

Method	Average Case	Worst Case	Average Case	Worst Case
Selection Sort	N*N/2	N*N/2	N	N
Insertion Sort	N*N/4	N*N/2	N*N/8	N*N/4
Bubble Sort	N*N/2	N*N/2	N*N/2	N*N/2
Shell Sort	N^{1.25}	N^(3/2)	?	?
Quicksort	2*NlogN	N*N/2	N	N