Data Structures and Algorithms
CS 503

Quiz 4, 2 May 2011

1. When quicksort is driven to worst-case behavior, which worst-case O(n²) sort does it most resemble in terms of data handling? Justify your answer.

   ---

   In terms of both data movement and data comparisons, worst-case quicksort is most like selection sort. Both scan through the O(n) data on each pass, comparing each element scanned, and swap two elements at the end of each scan. Both insertion sort and bubble sort do too many data movements, potentially up to O(n), per scan, and insertion sort may perform fewer comparisons per scan than does worst-case quicksort.

2. Does it make sense to use quadratic probing to resolve collisions in chained hash tables? Justify your answer.

   ---

   Not in the least. Collisions in a chained hash table are handled by adding another element to the linked list associated with the bucket to which element hashed; there's no need to use any kind of probe sequence to hop around the scatter table looking for an open bucket.

3. Radix sort is analogous to repeatedly sorting cards into piles. When using this analogy to implement radix sort, what data structure is most suitable for implementing the piles? Justify your answer.

   ---

   The important point to carry across from the card-sorting analog to the radix-sort implementation is that the cards must be kept in order as the piles are manipulated. The order in which cards are added to a pile must be the order in which the cards are removed from the pile; this preserves the order of the digits already sorted. First-in, first-out behavior is simply and most efficiently provided by a queue.

4. True or false: if a key space K is smaller than the scatter-table size for hash table H, then the keys from K will never collide when stored in H. Justify your answer.

   ---

   False. Collisions are determined by two factors: the scatter-table size and the hash function, and the scatter-table size has only indirect influence on the hash function. Even when the scatter-table size is large enough to avoid the pigeon-hole principle, the hash function may still map two different keys to the same index.

5. Each column below represents a sequence of snapshots of an array being sorted; each snapshot is taken after a pair of elements in the array have been swapped, and a snapshot is taken after every swap. Identify the sorts. Justify your answers.

   Note: One of the sorts used below wasn’t presented in class, although it may have been discussed in your textbook. You may call this sort “sort x.” The other three sorts were presented in class.

   a)	24351	b)	24351	c)	24351	d)	24351
   	24315		23451		14352		21354
   	24135		23415		12354		12354
   	21435		23145		12345		12345
   	12435		21345
   	12345		12345

   ---

   a) Bubble sort, as witnessed 1 shifting left element-by-element.

   b) Insertion sort, as witnessed the 3 shifting left into ascending order, followed by the 1.

   c) Selection sort, as witnessed by 1 and 2 swapping places, followed by 2 and 4.

   c) Sort x (Shell sort), as witnessed by 1 and 4 swapping places (gap size is 2), followed by 1 and 2, and 4 and 5 swapping places (gap size is 1).