Sorting Arrays

Sorting, like searching, is a common task in computer programming. Many different algorithms have been developed for sorting. This section introduces an intuitive sorting algorithm: selection sort.

Suppose that you want to sort a list in ascending order. Selection sort finds the smallest number in the list and swaps it with the first element. It then finds the smallest number remaining and swaps it with the second element, and so on, until only a single number remains. Figure below shows how to sort the list {2, 9, 5, 4, 8, 1, 6} using selection sort.

You know how the selection-sort approach works. The task now is to implement it in Java. Beginners find it difficult to develop a complete solution on the first attempt. Start by writing the code for the first iteration to find the smallest element in the list and swap it with the first element, and then observe what would be different for the second iteration, the third, and so on. The insight this gives will enable you to write a loop that generalizes all the iterations.

The solution can be described as follows:

for (int i = 0; i < list.length - 1; i++) {
select the smallest element in list[i..list.length-1];
swap the smallest with list[i], if necessary;
// list[i] is in its correct position.
// The next iteration applies on list[i+1..list.length-1]
}

Below implements the solution:

The selectionSort(double[] list) method sorts any array of double elements. The method is implemented with a nested for loop. The outer loop (with the loop control variable i) (line 12) is iterated in order to find the smallest element in the list, which ranges from list[i] to list[list.length-1], and exchange it with list[i].

The variable i is initially 0. After each iteration of the outer loop, list[i] is in the right place. Eventually, all the elements are put in the right place; therefore, the whole list is sorted.