Module 3 Problem Set
1. [10 pts] Show with a sample trace how selection sort sorts the letters
T H I S Q U E S T I O N
2. [10 pts] Show with a sample trace how insertion sort sorts the letters
T H I S Q U E S T I O N
3. [10 pts] Show with a sample trace how shell sort with the h-sequence 5,2,1
sorts the letters
M U C H L O N G E R Q U E S T I O N
4. [10 pts] If all keys are identical, does insertion sort work better than
selection sort? Justify your answer.
5. [10 pts] If all keys are in reverse order, does insertion sort work better than
selection sort? Justify your answer.
6. [10 pts] You are given a list of items with duplicates. Indicate how you
would use sorting to produce a list of unique items.
7. [10 pts] You are given a list of words. Some of the words are jumbles of
other words. For example: "caring" and "racing" are jumbles. How would you
use sorting to identify the jumbles in the list?
Give pseudocode (or real code if you want) that reads in a list of words, and
prints each set jumbles on 1 line. For example, if the input file is:
racing
secura
saucer
caring
random
Your output would be:
racing caring
secura saucer
random
The order does not matter.
8. [20 pts] Explain why the h-sequence 1, 2, 4, 8, 16, ..., 2^k is bad for shell
sort. Find an example where the worst case happens.
9. [10 pts] Why not use selection sort for h-sorting in shell sort?
