Selection Sort
Definition
Selection sort works by repeatedly finding the remaining minimum value in the array and swapping it to the front.
Algorithm
- For each index in the array:
- Find minimum value in the remainder of the array.
- Swap the min with the value in the current index.
- Add 1 to the index.
- 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
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.