Selection Sort

Definition

Selection sort works by repeatedly finding the remaining minimum value in the array and swapping it to the front.

Algorithm

  1. For each index in the array:
  2. Find minimum value in the remainder of the array.
  3. Swap the min with the value in the current index.
  4. Add 1 to the index.
  5. Repeat steps 2-4

Code

public static void selectionSort(int[] x){
    for (int i = 0; i < x.length; i++){
        swap(x,i,findMin(x,i));
    }
}
 
public static int findMin(int[] x, int start){
    int min = start;
    for(int i = start + 1; i < x.length; i++){
        if (x[i] < x[min]){
            min = i;
        }
    }
    return min;
}
 
public static void swap(int[] x, int i, int j){
    int temp = x[i];
    x[i] = x[j];
    x[j] = temp;
}

Visual Selection Sort

selec.bmp

Runtime

Selection sort runs O(n2) because it has a nested loop. Since it has to has to do n steps for each of the n numbers, the runtime is O(n2). It should be noted that the runtime is n2 no matter what the original order of the elements were. Selection sort will always go through all of its steps.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License