• 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

• The Algorithm:
  • Iteratively select the largest value in the list and swap it with the element at the bottom of the list, moving the bottom up by one
• Compared to Bubble Sort:
  • The bubble sort tends to move many more elements than does the selection sort
  • The bubble sort "painstakingly" moves an element to the top by swapping adjacent elements rather than by searching and making only one swap

• The Array to Sort:
  • The six-element array (8, 4, 7, 3, 9, 3)
• Iteration 1:
  • The 9 in element 4 is swapped with the 3 in element 5 and the bottom is moved up to 4
  • Note that this requires an inner loop that searches through all of the elements in the array

  • 8

    4

    7

    3

    3

    9

• Iteration 2:
  • The 8 in element 1 is swapped with the 3 in element 4 and the bottom is moved up to 3

  • 3

    4

    7

    3

    8

    9

• The Remaining Iterations:

  • 3

    4

    3

    7

    8

    9

    3

    3

    4

    7

    8

    9

    3

    3

    4

    7

    8

    9

• The Outer Loop:
  • Always \(n-1\) iterations
• The Inner Loop:
  • The first time through the inner loop iterates \(n-1\) times
  • The second time through the inner loop iterates \(n-2\) times
  • ...

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

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