Selection Sort

• Iterate through the elements in the list and find the minimal element in the list
• Swap the minimal element with the “first” element
• Repeat the process on the remaining n - 1 elements
• Note: Selection sort is not stable, an example: $2_a,2_b,1,5$; the first swap would result in $1,2_b,2_a,5$

Pseudocode

Analysis

• Comparison performed: once, inner loop, outer loop
• In total:
$$\sum_{i=1}^{n-1} \sum_{j=(i+1)}^n 1 = n(n-1)-\sum_{i=1}^{n-1} i=n(n-1)- \frac{n(n-1)}{2}=\frac{n(n-1)}{2}$$
• Selection Sort is $O(n^2)$

Code Samples

Code Sample 11: Java Selection Sort for integers

public static void selectionSort (int array []) {
  int n = array.length;
  for (int i=0; i<n; i++) {
    int index_of_min = i;
    for(int j=i; j<n; j++){
      if( array[index_of_min] > array [j]){
        index_of_min = j;
      }
    }
    int temp = array[i];
    array[i] = array[index_of_min];
    [index_of_min] = temp;
  }
}