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.
19.7.2 Efficiency of the Insertion Sort
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 ).
19.8 Merge Sort
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.
 
 
 
Search WWH ::




Custom Search