Java Reference
In-Depth Information
@param first an integer >= 0 and < a.length that is the index of
the first array entry to consider
@param last an integer >= first and < a.length that is the
index of the last array entry to consider
@return the index of the smallest value among
a[first], a[first + 1], . . . , a[last] */
private static
<T
extends
Comparable<?
super
T>>
int
getIndexOfSmallest(T[] a,
int
first,
int
last)
{
T min = a[first];
int
indexOfMin = first;
for
(
int
index = first + 1; index <= last; index++)
{
if
(a[index].compareTo(min) < 0)
{
min = a[index];
indexOfMin = index;
}
// end if
// Assertion: min is the smallest of a[first] through a[index].
}
// end for
return
indexOfMin;
}
// end getIndexOfSmallest
/** Swaps the array entries a[i] and a[j].
@param a an array of objects
@param i an integer >= 0 and < a.length
@param j an integer >= 0 and < a.length */
private static void
swap(Object[] a,
int
i,
int
j)
{
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// end swap
}
// end SortArray
Question 1
Trace the steps that a selection sort takes when sorting the following array into
ascending order: 9 6 2 4 8.
Selection sort also has a natural recursive form. Often recursive algorithms that involve arrays operate
on a portion of the array. Such algorithms use two parameters,
first
and
last
, to designate the portion
of the array containing the entries
a[first]
through
a[last]
. The method
getIndexOfSmallest
in
Listing 8-1 illustrates this technique. The recursive selection sort algorithm uses this notation as well:
