Selection Sort

Another application for nested loops is a sorting algorithm called Selection Sort. Sorting is a task that we do every day, whether it’s organizing our bookshelf or doing a Google search (Google sorts search results based on an algorithm).

Watch this video (from time 0:00 to 7:48 only) to learn about Selection Sort, an inefficient but simple sorting algorithm. You can also watch this shorter video (~3 minutes) if you’re already familiar with Selection Sort.

https://www.youtube-nocookie.com/embed/GUDLRan2DWM

https://www.youtube-nocookie.com/embed/g-PGLbMth_g

Here is the code for Selection Sort (for an array of integers):

public class SelectionSort {

    public static void main(String[] args) {
        int[] list = { 5, 25, -1, 2, 9, 5, -4 };

        // goes up to index list.length - 1
        // because you don't need to check last element
        // since it will be sorted already
        for (int i = 0; i < list.length - 1; i++) {
            int min = list[i];
            int minIndex = i;

            // find the current smallest element
            for (int j = i + 1; j < list.length; j++) {
                if (list[j] < min) {
                    min = list[j];
                    minIndex = j;
                }
            }

            // swap it with whatever is in the
            // first position of unsorted array if needed
            if (minIndex != i) {
                int temp = list[i];
                list[i] = min;
                list[minIndex] = temp;
            }
        }

        // print the sorted array
        for (int n : list) {
            System.out.print(n + " ");
        }
        System.out.println(); // move cursor to next line
    }
}

Output of the code above:

-4 -1 2 5 5 9 25

Practice

Test Selection Sort

Create a driver class called TestSelectionSort which prompts the user to enter the length of an array and the elements (doubles) in the array. Then, your program should use selection sort to sort the array in place, and then print the resulting array.

Example output:

Enter the length of the array: 5
Enter the elements in the array: -1 236.3 2 6 0
-1.0 0.0 2.0 6.0 236.3