Short Answers Section 12.1 Quadratic Sorting Algorithms |
5 3 8 9 1 7 0 2 6 4Draw this array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest).
5 3 8 9 1 7 0 2 6 4Draw this array after the FIRST iteration of the large loop in an insertion sort (sorting from smallest to largest). This iteration has shifted at least one item in the array!
void selectionsort(int[ ] data, int first, int n);Your program also has an integer array called x, with 10 elements. Write two method activations: The first activation uses selectionsort to sort all of x; the second call uses selectionsort to sort x[3]..x[9].
Short Answers
Section 12.2
Recursive Sorting
Algorithms
3, 0, 2, 4, 5, 8, 7, 6, 9Which of these elements could be the pivot? (There may be more than one possibility!)
5 3 8 9 1 7 0 2 6 4Suppose we partition this array using quicksort's partition function and using 5 for the pivot. Draw the resulting array after the partition finishes.
5 3 8 9 1 7 0 2 6 4Draw this array after the TWO recursive calls of merge sort are completed, and before the final merge step has occured.
private static void merge(int[ ] data, int first, int n1, int n2); // Precondition: data has at least n1+n2 components starting at // data[first]. The first n1 elements (from data[first] to // data[first+n1-1]) are sorted from smallest to largest, and the last // n2 elements (from data[first+n1] to data[first+n1+n2-1]) are also // sorted from smallest to largest. // Postcondition: Starting at data[first, n1+n2 elements of data have been // rearranged to be sorted from smallest to largest.
Short Answers
Section 12.3
An O(n log n) Algorithm
Using a Heap
Worst Case | Average Case | |
Binary search of a sorted array | . | . |
Insertion sort | . | . |
Merge sort | . | . |
Quick sort without "median of three" pivot selection | . | . |
Quick sort with "median of three" pivot selection | . | . |
Selection sort | . | . |
Heap sort | . | . |
Multiple Choice Section 12.1 Quadratic Sorting Algorithms |
1 2 3 4 5 0 6 7 8 9Which statement is correct? (Note: Our selectionsort picks largest items first.)
2 4 5 7 8 1 3 6Which statement is correct? (Note: Our selectionsort picks largest items first.)
Multiple Choice
Section 12.2
Recursive Sorting
Algorithms
2 5 1 7 9 12 11 10Which statement is correct?
Multiple Choice
Section 12.3
An O(n log n) Algorithm
Using a Heap
6 4 5 1 2 7 8How many reheapifications downward have been performed so far?