Java Reference
In-Depth Information
after pass 9: 12 16 30 34 40 45* 50 80 87 96
-- -- -- -- -- -- -- -- -- --
Sorted array:
[12, 16, 30, 34, 40, 45, 50, 80, 87, 96]
Fig. 19.5
|
Sorting an array with insertion sort. (Part 3 of 3.)
Method
insertionSort
Lines 9-28 declare the
insertionSort
method. Lines 12-27 loop over
data.length
-
1
items in the array. In each iteration, line 14 declares and initializes variable
insert
, which
holds the value of the element that will be inserted into the sorted portion of the array.
Line 15 declares and initializes the variable
moveItem
, which keeps track of where to insert
the element. Lines 18-23 loop to locate the correct position where the element should be
inserted. The loop will terminate either when the program reaches the front of the array
or when it reaches an element that's less than the value to be inserted. Line 21 moves an
element to the right in the array, and line 22 decrements the position at which to insert
the next element. After the loop ends, line 25 inserts the element into place.
Method
printPass
The output of method
printPass
(lines 31-51) uses dashes to indicate the portion of the
array that's sorted after each pass. An asterisk is placed next to the element that was insert-
ed into place on that pass.
The insertion sort algorithm also runs in
O
(
n
2
) time. Like selection sort, the implementa-
tion of insertion sort (lines 9-28) contains two loops. The
for
loop (lines 12-27) iterates
data.length
-
1
times, inserting an element into the appropriate position in the elements
sorted so far. For the purposes of this application,
data.length
-
1
is equivalent to
n
- 1
(as
data.length
is the size of the array). The
while
loop (lines 18-23) iterates over the
preceding elements in the array. In the worst case, this
while
loop will require
n
- 1 com-
parisons. Each individual loop runs in
O
(
n
) time. In Big O notation, nested loops mean
that you must
multiply
the number of comparisons. For each iteration of an outer loop,
there will be a certain number of iterations of the inner loop. In this algorithm, for each
O
(
n
) iterations of the outer loop, there will be
O
(
n
) iterations of the inner loop. Multiply-
ing these values results in a Big O of
O
(
n
2
).
Merge sort
is an
efficient
sorting algorithm but is conceptually
more complex
than selection
sort and insertion sort. The merge sort algorithm sorts an array by
splitting
it into two
equal-sized subarrays,
sorting
each subarray, then
merging
them into one larger array. With
an odd number of elements, the algorithm creates the two subarrays such that one has one
more element than the other.
The implementation of merge sort in this example is recursive. The base case is an
array with one element, which is, of course, sorted, so the merge sort immediately returns
in this case. The recursion step splits the array into two approximately equal pieces, recur-
sively sorts them, then merges the two sorted arrays into one larger, sorted array.