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*(n^{2}) 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*(n^{2}). It should be noted that the runtime is n^{2} no matter what the original order of the elements were. Selection sort will always go through all of its steps.