Arrays - Java - page 376

EXAMPLE: Sorting an Array

In this example, we define a method called sort that will sort a partially filled array of
numbers so that they are ordered from smallest to largest.
The procedure sort has one array parameter, a . The array a will be partially filled,
so there is an additional formal parameter called numberUsed , which tells how many
array positions are used. Thus, the heading for the method sort will be

public static void sort( double [] a, int numberUsed)

The method sort rearranges the elements in array a so that after the method call is
completed, the elements are sorted as follows:

≤ a[1] ≤ a[2] ≤ ... ≤ a[numberUsed − 1]

a[0]

The algorithm we use to do the sorting is called selection sort . It is one of the easiest
of the sorting algorithms to understand.
One way to design an algorithm is to rely on the definition of the problem. In this
case, the problem is to sort an array a from smallest to largest. That means rearranging
the values so that a[0] is the smallest, a[1] the next smallest, and so forth. That defini-
tion yields an outline for the selection sort algorithm:

for ( int index = 0; index < numberUsed; index++)
Place the index th smallest element in a[index]

There are many ways to realize this general approach. The details could be developed
by using two arrays and copying the elements from one array to the other in sorted
order, but using one array should be both adequate and economical. Therefore, the
method sort uses only the one array containing the values to be sorted. The method
sort rearranges the values in the array a by interchanging pairs of values. Let us go
through a concrete example so that you can see how the algorithm works.
Consider the array shown in Display 6.10. The selection sort algorithm will place the
smallest value in a[0] . The smallest value is the value in a[4] . So the algorithm inter-
changes the values of a[0] and a[4] . The algorithm then looks for the next smallest ele-
ment. The value in a[0] is now the smallest element, so the next smallest element is the
smallest of the remaining elements a[1] , a[2] , a[3] ,..., a[9] . In the example in Display
6.10, the next smallest element is in a[6] , so the algorithm interchanges the values of
a[1] and a[6] . This positioning of the second smallest element is illustrated in the
fourth and fifth array pictures in Display 6.10. The algorithm then positions the third
smallest element, and so forth. As the sorting proceeds, the beginning array elements are
set equal to the correct sorted values. The sorted portion of the array grows by adding
elements one after the other from the elements in the unsorted end of the array. Notice
that the algorithm need not do anything with the value in the last indexed variable,
a[9] , because once the other elements are positioned correctly, a[9] must also have the
correct value. After all, the correct value for a[9] is the smallest value left to be moved,
and the only value left to be moved is the value that is already in a[9] .