• 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

• 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

• 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) \)