Understanding Selection Sort - Algorithm, Analysis, and Java Implementation

Selection Sort

• Iterate through the elements in the list and find the minimal element in the unsorted portion.
• Swap the minimal element with the “first” element of the unsorted portion.
• Repeat the process on the remaining $n - 1$ elements.
• Note: Selection sort is not stable. For example, consider the sequence $2_a, 2_b, 1, 5$; the first swap would result in $1, 2_b, 2_a, 5$, changing the relative order of the $2$s.

Pseudocode

Analysis

• Comparisons performed: once in the inner loop, executed multiple times by the 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 has a time complexity of $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 + 1; j < n; j++) { // Start inner loop from i+1
      if (array[index_of_min] > array[j]) {
        index_of_min = j;
      }
    }
    int temp = array[i];
    array[i] = array[index_of_min];
    array[index_of_min] = temp; // Corrected missing array variable
  }
}