Selection Sort

Key Idea

Each outer loop selects the smallest element and places it in the beginning.

Code

public void selectionSort(int[] arr) { 
    int smallest;
    for (int i = 0; i < arr.length - 1; i++) {
        smallest = selectSmallest(arr, i);
        swap(arr, smallest, i);
    }
}

// return the index of the smallest element in that subarray
private int selectSmallest(int arr[], int start) {
    int minimum = start;
    for (int i = start + 1; i < arr.length; i++) {
        if (arr[i] < arr[minimum]) {
            minimum = i;
        }
    }
    return minimum;
}

Time Complexity

The analysis is similar to bubble sort. O(n^2).