String Sorts

Exercise 1: Key-indexed counting warm-up (10 points)

Consider the items (A,2), (B,1), (C,0), (D,3), (E,2), (F,1), (G,0), where the second component is an integer key in the range 0 to 3.

1. Compute the frequency counts for the keys 0, 1, 2, and 3.
2. Transform these counts into starting indices as in key-indexed counting.
3. Give the final stable order of the items after sorting by the integer key.

Exercise 2: LSD string sort trace (14 points)

Consider the fixed-length keys no is th ti fo al go pe to co to th ai of th pa.

1. Show the array after the LSD pass for d = 1.
2. Show the array after the LSD pass for d = 0.
3. Briefly explain why stability is essential for LSD string sort.
4. Does the basic LSD algorithm from the lecture work unchanged for variable-length strings? Briefly justify your answer.

Exercise 3: MSD and 3-way string quicksort (12 points)

Consider the keys now is the time for all good people to come to the aid of.

1. In MSD string sort at depth d = 0, which non-empty subarrays result after the first partitioning step? List the groups in sorted order by their first character.
2. Explain why a cutoff to insertion sort is an important optimization for MSD string sort.
3. State two practical advantages of 3-way string quicksort over plain MSD string sort.
4. State one situation in which MSD string sort is still attractive.

Exercise 4: Implementation of 3-way string quicksort (24 points)

Implement a program Quick3String.py that sorts an arbitrary number of strings in ascending lexicographic order using 3-way string quicksort.

The program should follow these requirements:

• The strings are passed as command-line arguments.
• Use a helper function charAt(s, d) that returns the d-th character code and -1 at end-of-string.
• Use 3-way partitioning on the d-th character.
• Add a cutoff to insertion sort for small subarrays.
• Print the sorted strings, one per line.
• Do not use Python's built-in sorted() or list.sort() for the actual sorting step.

Example:

python3 Quick3String.py she sells seashells by the sea shore
by
sea
seashells
sells
she
shore
the

Submit the source code together with your written answers.