CS 503 Quiz 2

CS 503, Advanced Programming I

Quiz 2, 14 February 2006

Quicksort's recursive overhead is high enough to make quicksort a bad choice for sorting arrays of twenty elements or less. The overhead also implies that, when sorting larger arrays, quicksort should stop when the partition size is reduced to around twenty elements; leaving an almost sorted array that can be dealt with more efficiently by another sort.
Which of bubble sort, selection sort, and insertion sort would be a good choice to finish up the sort once quicksort stops? Explain your answer.
The incomplete quicksort leaves the data inter-block sorted (any value in a before block is greater than any value in an after block, assuming ascending order) but not intra-block sorted (a before value in a block may be greater than an after value from the same block).
All of bubble, selection, and insertion sorts use O(n²) time, so that's no help without more detail. Bubble and selection sort make O(n) comparisons on each pass, while insertion sort makes only O(1) comparisons (insertion sort scans at most one block on each pass, and the block-size in elements is a constant).
During each pass bubble sort makes O(n) assignments, and insertion and selection sorts each makes O(1) assignments (insertion sort potentially makes b assignments, but b is a constant).
Given a block-sorted array, bubble sort still makes O(n²) comparisons and assignments, selection sort still makes O(n²) comparisons and O(n) assignments, but insertion sort makes only O(n) comparisons and assignments, suggesting that insertion sort is the best sort to use.
Answers to this question were mostly vague, but in the general area of the right answer.
What is the relation between natural merge-sorting and replacement selection in external sorting?
Straight merge sort divides the data to be sorted in half without considering the data being sorted. Sort merge forms blocks in the same way, without considering the data being sorted.
Replacement selection pays attention to data order when forming blocks, ending one block and starting another when encountering an out-of-order values. Natural merge-sort forms runs in the same way, stopping one run and starting another when it encounters an out-of-order value.
Natural merge sorting and replacement selection both share the feature of paying attention to the order of the data being divided up.
Most answers mis-identified the natural merge sort.
Your job is to sort an array of records, each key of which is either the value a or the value b. Describe the most time- and space- efficient sort for your job.
From our discussion of radix-exchange sort, a partition is equivalent to a sort when only two values are involved. A partition requires no extra space and exactly one pass through the data, and you can't get more efficient than that without some extra knowledge.
Most of the answers to this question were wrong. Some answers mentioned some kind of radix sort, but none mentioned partitioning specifically.
The second programming assignment pointed out that the strings "boot" and "boat" would always collide. Describe the modifications you would make to the hash function used in the assignment to eliminate this kind of collision.
One way to modify the hash function is to use a different set of letters, such as the first and second or last and next-to-last characters. This, however, only shifts the collision to a different set of letters. Another possibility is to use all the letters in the hash function; this reduces collisions but has several problems, some of which we'll discuss when we get to hashing.
Most of the answers to this question were right.

This page last modified on 17 February 2006.