Java Reference
In-Depth Information
public static int findMin( int a[] , int start)
{
int minIndex = start ;
for ( int i = start ; i < a . l e n g t h ;
i ++)
{
if (a[ i ] < a [minIndex ])
{
minIndex = i ;
}
return minIndex ;
}
public static void swap( int a[] , int i, int j) {
int temp = a [ i ] ;
a[i] =a[j];
a[j] = temp;
}
public static void selectionSort( int start , int [] a)
{
if (start == a. length 1)
{
return ;
int j = findMin(a, start);
swap(a, start , j) ;
selectionSort(start + 1, a);
}
}
The selectionSort method takes as input the start index. The end index does not
change and therefore there is no need to pass it as a parameter to the method. The base case
is when the start and the end indexes are the same, that is, the array has a single element.
If we do not have the base case, then our code finds the index of the smallest element
and swaps this element with the first element in the current array. Then the algorithm is
recursively applied to the rest of the array. Note that we have added a method that swaps
two elements in an array and a method that finds the index of the smallest number in an
array. The method for swapping two elements in an array can be quite useful in a sorting
algorithm. If we had created this method during the coding of the bubble sort algorithm,
then we would not have to write the code again.
We again have a case of tail recursion. A non-recursive solution of the problem is shown
next.
public static void selectionSort( int start , int [] a)
{
while ( true )
{
if (start == a. length 1)
{
return ;
int j = findMin(a, start);
swap(a, start , j) ;
start++;
}
}
The method runs roughly as eciently as the bubble sort. The main difference is that
instead of moving the biggest element to the end, the method moves the smallest element
to the front.

Search WWH ::

Custom Search