• A Popular Motivation:
  • Between 25% and 50% of computing time in commercial applications is devoted to sorting
  • Hence, it is important to consider the efficiency of sorting algorithms
• My Motivation:
  • The issues that arise are illustrative of the issues that arise when developing other algorithms
  • They provide good examples of how to find the efficiency of an algorithm

• An Analogy:
  • The way people sort cards when playing poker or rummy
• The Algorithm:
  • Sort the first two elements
  • Then, take the third element and put it in the appropriate position relative to the first two
  • Proceed iteratively until all of the elements are sorted

    insertionsort(a[])
    {
      for all i {

        move all elements larger than a[i] one position;
        put a[i] in the resulting "hole";
      }
    }
  

• The Array to Sort:
  • The six-element array (8, 4, 7, 3, 9, 3)
• Iteration 1:
  • Sort the first two elements as follows:

  • 4

    8

    7

    3

    9

    3

• Iteration 2:
  • The 7 in element 2 is put in the proper position relative to elements 0 and 1
  • Specifically, the 4 in position 0 is left where it is, the 8 in position 1 is moved up one, and the 7 is put in the "hole" (i.e., position 1)

  • 4

    7

    8

    3

    9

    3

• Iteration 3:
  • The 3 in element 3 must be put in the proper position relative to elements 0, 1 and 2
  • Specifically, the 4, 7, and 8 are all shifted up 1 position and the 3 is put in the "hole" (i.e., position 0)

  • 3

    4

    7

    8

    9

    3

• The Remaining Iterations:

  • 3

    4

    7

    8

    9

    3

    3

    3

    4

    7

    8

    9

cppexamples/sorting/InsertionSort.cpp

/**
 * Sort an array of integers using an insertion sort.
 *
 * Side Effects: The array is sorted  "in place".
 *
 * @param a        The array of integers
 * @param length   The number of elements in the array
 */
void sort(int a[], int length) {
  int i, j, temp;

  for (i = 1; i < length; i++) {
    temp = a[i];

    j = i;
    while ((j > 0) && (temp < a[j - 1])) {
      a[j] = a[j - 1];
      j--;
    }

    a[j] = temp;
  }
}
        

• The Outer Loop:
  • Always \(n-1\) iterations
• The Inner Loop:
  • The worst case is when the array is in reverse order
  • In this case, the first outer loop requires 1 move, the second outer loop requires 2 moves, etc...

\( T(n) = 1 + 2 + \cdots + (n-1) = n \cdot (n-1)/2 \)

So: \( T(n) = O(n^2) \)