We've seen a number of sorting algorithms in the last few weeks: selection sort, insertion sort, mergesort, quicksort, and heapsort. Describe the advantages and disadvantages of each.
As we merge sort the following, what will the array look like just before performing the last merge?
35 57 53 26 50 15 22 21 25 14 11 2
Consider the algorithm we outlined in class for merging two lists. In the worst case, how many element comparisons will this algorithm take to merge an array with n elements and an array of m elements? The answer should be exact; do not use big-O or Theta notation to approximate.
Using the algorithm we outlined in class, what will be the result after we pivot on 35?
35 57 53 26 50 15 22 21 25 14 11 2
Challenge problem: For an array with n elements, what is the maximum number of swaps that the algorithm we outlined in class will perform during a pivot operation? Do not use big-O or Theta notation.
Heapify the following using the algorithm we outlined in class. The heap should have the maximum element at the top of the heap.
35 57 53 26 50 15 22 21 25 14 11 2
After heapsort heapifies, it then begins removing things from the top of the heap and placing them at the end of the array. How will your answer from the above question look after four iterations?
Say we have a heap priority queue implementation and its array is currently
51 46 34 31 39 29 7 14 3 1 35 2How will it look after we insert 42?
Challenge problem: Consider a map (graph) where each edge has a nonnegative length. Say we want to find the shortest distance from one vertex to all the rest. (This is the problem we considered in Mon 29 Sep recitation.) How can you use priority queues to find this?
How does the following list look after the first iteration of radix sort's outer loop?
class leaks every other refer embed array
Is the following select sort routine for sorting by the kth letter of an array of strings stable? If so, explain why. If not, give a simple example of three or four words on which it fails.
for(int i = n - 1; i > 0; i--) {
int max = i;
for(int j = 0; j < i; j++) if(A[j][k] >= A[max][k]) max = j;
int t = A[i]; // swap what's at i and what's at j
A[i] = A[max];
A[max] = t;
}