Java Reference
In-Depth Information
smallest
will contain the index of the smallest element in the remaining array. Line 21
calls method
swap
(lines 27-32) to place the smallest remaining element in the next or-
dered spot in the array.
Methods
printPass
The output of method
printPass
uses dashes (lines 52-53) to indicate the portion of the
array that's sorted after each pass. An asterisk is placed next to the position of the element
that was swapped with the smallest element on that pass. On each pass, the element next
to the asterisk (specified at line 43) and the element above the rightmost set of dashes were
swapped.
The selection sort algorithm runs in
O
(
n
2
) time. Method
selectionSort
(lines 9-24)
contains two
for
loops. The outer one (lines 12-23) iterates over the first
n
- 1 elements
in the array, swapping the smallest remaining item into its sorted position. The inner loop
(lines 17-19) iterates over each item in the remaining array, searching for the smallest el-
ement. This loop executes
n
- 1 times during the first iteration of the outer loop,
n
- 2
times during the second iteration, then
n
- 3, …, 3, 2, 1. This inner loop will iterate a total
of
n
(
n
-1)/2 or (
n
2
-
n
)/2. In Big O notation, smaller terms drop out and constants are
ignored, leaving a Big O of
O
(
n
2
).
Insertion sort
is another
simple, but inefficient
, sorting algorithm. The first iteration of this
algorithm takes the
second element
in the array and, if it's
less than
the
first element
,
swaps
it with the first element
. The second iteration looks at the third element and inserts it into
the correct position with respect to the first two, so all three elements are in order. At the
i
th iteration of this algorithm, the first
i
elements in the original array will be sorted.
Consider as an example the following array, which is identical to the one used in the
discussions of selection sort and merge sort.
34 56 4 10 77 51 93 30 5 52
A program that implements the insertion sort algorithm will first look at the first two ele-
ments of the array, 34 and 56. These are already in order, so the program continues. (If
they were out of order, the program would swap them.)
In the next iteration, the program looks at the third value, 4. This value is less than
56, so the program stores 4 in a temporary variable and moves 56 one element to the right.
The program then checks and determines that 4 is less than 34, so it moves 34 one element
to the right. The program has now reached the beginning of the array, so it places 4 in the
zeroth element. The array now is
4 34 56 10 77 51 93 30 5 52
In the next iteration, the program stores 10 in a temporary variable. Then it compares 10
to 56 and moves 56 one element to the right because it's larger than 10. The program then
compares 10 to 34, moving 34 right one element. When the program compares 10 to 4,
it observes that 10 is larger than 4 and places 10 in element 1. The array now is
4 10 34 56 77 51 93 30 5 52
