JMU
Selection Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Motivation
Selection Sort
An Example
An Implementation
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;
  }
}
        
Efficiency Analysis
Efficiency Analysis (cont.)

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

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