Comment on page

# 35.5 Exercises

## Factual

1. 1.
If we use counting sort to sort all 61B students by the number of siblings they have, how long will the counting array be? Let
$N$
be the total number of students and
$M$
be the maximum number of siblings a student has.
2. 2.
When performing a radix sort like LSD or MSD, which of the following sorting algorithms could we use for each digit?
• Counting sort
• Heapsort
• Mergesort
• Selection sort
3. 3.
If we're sorting N lowercase english strings using MSD sort, what is the maximum number of subproblems after considering only the the most significant digit?
Problem 1
The counting array will have
$M$
entries. In general for counting sort, the count array's length only needs to be equal to the maximum number of unique elements we are counting.
Problem 2
Recall that the sub-sort for each digit must be stable. This rules out heapsort and selection sort.
• Counting sort
• Heapsort
• Mergesort
• Selection sort
Problem 3
26, since there are 26 possible values for the first digit we're sorting on.

## Metacognitive

1. 1.
What are some advantages of counting sort over quicksort?
2. 2.
Why do we use LSD over counting sort?
3. 3.
If we use MSD radix sort, we start with a single problem of size N, where N is the number of strings. Depending on the results on the most significant digit, we end up with a larger number of smaller subproblems, i.e. we're doing some divide and conquer. In the worst case, we end up with only one subproblem, also of size N. When does this happen?
Problem 1
Counting sort is technically faster than LSD, since counting sort doesn't require splitting up items by digits/letters. However, counting sort can require extremely large amounts of memory in some cases (for example, when sorting Strings, you need one entry in an array for every possible String).