• 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

cppexamples/sorting/SelectionSort.cpp

/**
 * Sort an array of integers using a selection 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 bottom, i, indexOfMax, temp;

  for (bottom = length - 1; bottom >= 1; bottom--) {
    indexOfMax = 0;

    for (i = 1; i <= bottom; i++) {
      if (a[i] > a[indexOfMax])
        indexOfMax = i;
    }

    temp = a[bottom];
    a[bottom] = a[indexOfMax];
    a[indexOfMax] = temp;
  }
}
        

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