Arrays - Absolute Java - page 388

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[0] ≤ a[1] ≤ a[2] ≤ ... ≤ a[numberUsed - 1]
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 definition yields an outline for the selection sort algorithm:
for ( int index = 0; index < numberUsed; index++)
Place the indexth 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
interchanges the values of a[0] and a[4] . The algorithm then looks for the next
smallest element. 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] .