Java Reference
In-Depth Information
• Binary search runs in
O
(log
n
) time because each step removes half of the remaining elements;
this is also known as logarithmic run time (p. 820).
• If the array size is doubled, binary search requires only one extra comparison.
Section 19.6 Selection Sort
• Selection sort (p. 821) is a simple, but inefficient, sorting algorithm.
• The sort begins by selecting the smallest item and swaps it with the first element. The second iter-
ation selects the second-smallest item (which is the smallest remaining item) and swaps it with the
second element. The sort continues until the last iteration selects the second-largest element and
swaps it with the second-to-last element, leaving the largest element in the last index. At the
i
th
iteration of selection sort, the smallest
i
items of the whole array are sorted into the first
i
indices.
• The selection sort algorithm runs in
O
(
n
2
) time (p. 824).
Section 19.7 Insertion Sort
• The first iteration of insertion sort (p. 824) 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 in the correct position with respect to the first two elements. After the
i
th
iteration of insertion sort, the first
i
elements in the original array are sorted.
• The insertion sort algorithm runs in
O
(
n
2
) time (p. 827).
Section 19.8 Merge Sort
• Merge sort (p. 827) is a sorting algorithm that's faster, but more complex to implement, than se-
lection sort and insertion sort. The merge sort algorithm sorts an array by splitting it into two equal-
sized subarrays, sorting each subarray recursively and merging the subarrays into one larger array.
• Merge sort's base case is an array with one element. A one-element array is already sorted, so
merge sort immediately returns when it's called with a one-element array. The merge part of
merge sort takes two sorted arrays and combines them into one larger sorted array.
• Merge sort performs the merge by looking at the first element in each array, which is also the
smallest element in the array. Merge sort takes the smallest of these and places it in the first ele-
ment of the larger array. If there are still elements in the subarray, merge sort looks at the second
of these (which is now the smallest element remaining) and compares it to the first element in
the other subarray. Merge sort continues this process until the larger array is filled.
• In the worst case, the first call to merge sort has to make
O
(
n
) comparisons to fill the
n
slots in
the final array.
• The merging portion of the merge sort algorithm is performed on two subarrays, each of approx-
imately size
n
/2. Creating each of these subarrays requires
n
/2 - 1 comparisons for each subarray,
or
O
(
n
) comparisons total. This pattern continues as each level works on twice as many arrays,
but each is half the size of the previous array.
• Similar to binary search, this halving results in log
n
levels for a total efficiency of
O
(
n
log
n
) (p. 833).
Self-Review Exercises
19.1
Fill in the blanks in each of the following statements:
a)
A selection sort application would take approximately
times as long to run
on a 128-element array as on a 32-element array.
b) The efficiency of merge sort is .
19.2
What key aspect of both the binary search and the merge sort accounts for the logarithmic
portion of their respective Big Os?
