Note:  This quiz covers the following sorting algorithms:  bubblesort, heapsort, insertionsort, mergesort, quicksort, radixsort, selectionsort.

Question 1:   List all the quadratic sorts (for average case).

Question 2:   List all the n log n sorts (for average case).

Question 3:   Which sorting algorithm is n log n on average, but quadratic in its worst case?

Question 4:   Which sorting algorithm is quadratic on average, but linear (one-pass) in its best case?

Question 5:   Name the most efficient n log n sort, on average.

Question 6:   Say we invent a new sort, SuperFastSort, the fastest sort known on average.  What would you expect its average-case runtime to be (in terms of n, the number of elements in an unsorted vector)?

Question 7:   Say that it turns out that lowly Bubblesort is faster than SuperFastSort for small vectors.  Explain (very briefly) how this could happen.
 

For Questions 8-10, consider the following vector:

213   224   713   53   258   51   729

Question 8:   Provide a sequence of vectors, starting with that vector, and culminating in a sorted vector, demonstrating how radixsort works.

Question 9:   Provide a sequence of vectors, starting with that vector, and culminating in a sorted vector, demonstrating how heapsort works.

Question 10:   Provide a sequence of vectors, starting with that vector, and culminating in a sorted vector, demonstrating how quicksort works.

Question 11:   Write the signature for a function which itself takes another function as input.  Any such signature will do.