Announcement

Feel free to use LLMs (ChatGPT, etc) however you want on phase 2.

• Make sure to cite.

​

My OH are as normal today 2 - 3 in 779 Soda.

Radix Sorts

2

Lecture 35

CS61B, Spring 2023 @ UC Berkeley

Josh Hug and Justin Yokota

Today’s Two New Ideas

Today we’ll cover two new ideas:

• Digit-by-Digit Sorting
• A procedure that uses a sort (e.g. Merge Sort, Quicksort, Counting Sort).
• Using the word “sort” is arguably a misnomer.
• Digit-by-digit sorting is a process that uses another sort as a subroutine.
• Counting Sort
• A new type of sort that competes with Merge Sort, Quicksort, Heap Sort, Insertion Sort, Selection Sort, etc.
• Unlike these other sorts, Counting Sort does not use compareTo.

Warmup: Digit-by-digit Sorting

Lecture 35, CS61B, Spring 2023

Warmup: Digit-by-digit Sorting

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

What are the 4 integers at the end of the array?

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

I put 53 and 23 in this order. Would they always be in this order?

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

I put 53 and 23 in this order. Would they always be in this order?

• Not necessarily! Depends on if the sort I used is stable.
• Stable sort yields 53 then 23.
• Example: If I used Quicksort with shuffle, could have been 23 then 53.

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Now suppose we sort by the left digit using a stable sort.

In what order will 31,

32, 34, and 34 appear?

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Now suppose we sort by the left digit using a stable sort.

Digit-by-digit Sorting

This procedure does not work if the sort subroutine is unstable.

Digit-by-digit Sorting

Example of a digit-by-digit sort:

• Use a stable sort on each digit, moving from least to most significant.
• Result is guaranteed to correct!

Last digit is 3

Mid digit is 3

Top digit is 3

Digit-by-digit Sorting

Two quick notes:

• No obvious reason why this procedure is useful (can just sort by entire integer)
• Other digit-by-digit sort procedures work.

Last digit is 3

Mid digit is 3

Top digit is 3

We’ll come back to digit-by-digit sorting later!

The Counting Sort Algorithm

Lecture 35, CS61B, Spring 2023

Warmup: Digit-by-digit Sorting

Counting Sort

• The Counting Sort Algorithm
• Runtime

Radix Sorts:

• LSD Radix Sort
• MSD Radix Sort

Comparison Based Sorting

The key idea from our previous sorting lecture: Sorting requires Ω(N log N) compares in the worst case.

• Thus, the ultimate comparison based sorting algorithm has a worst case runtime of Θ(N log N).

​

From an asymptotic perspective, that means no matter how clever we are, we can never beat Merge Sort’s worst case runtime of Θ(N log N).

• ...but what if we don’t compare at all?

Example #1: Sleep Sort (for Sorting Integers) (not actually good)

For each integer x in array A, start a new program that:

• Sleeps for x seconds.
• Prints x.

​

All start at the same time.

​

Runtime:

• N + max(A)

​

Example #2: Counting Sort: Exploiting Space Instead of Time

Assuming keys are unique integers 0 to 11.

​

Idea:

• Create a new array.
• Copy item with key i into ith entry of new array.

Example #2: Counting Sort: Exploiting Space Instead of Time

Example #2: Counting Sort: Exploiting Space Instead of Time

Example #2: Counting Sort: Exploiting Space Instead of Time

Example #2: Counting Sort: Exploiting Space Instead of Time

Generalizing Counting Sort

We just sorted N items in Θ(N) worst case time.

• Avoiding yes/no questions lets us dodge our lower bound based on puppy, cat, dog!

​

Simplest case:

• Keys are unique integers from 0 to N-1.

​

More complex cases:

• Non-unique keys.
• Non-consecutive keys.
• Non-numerical keys.

Counting Sort: http://yellkey.com/seven

Alphabet case: Keys belong to a finite ordered alphabet.

• Example: {♣, ♠, ♥, ♦} (in that order)

​

​

​

​

​

​

​

​

​

​

Question: What will be the index of the first ♥?

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Alphabet case: Keys belong to a finite ordered alphabet.

• Example: {♣, ♠, ♥, ♦} (in that order)

​

​

​

​

​

​

​

​

​

​

Question: What will be the index of the first ♥?

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Implementing Counting Sort with Counting Arrays

Counting sort:

• Count number of occurrences of each item.
• Iterate through list, using count array to decide where to put everything.
• Interactive Demo

​

Bottom line, we can use counting sort to sort N objects in Θ(N) time.

Counting Sort Runtime

Lecture 35, CS61B, Spring 2023

Warmup: Digit-by-digit Sorting

Counting Sort

• Procedure
• Runtime

Radix Sorts:

• LSD Radix Sort
• MSD Radix Sort

Counting Sort vs. Quicksort: http://yellkey.com/just

For sorting an array of the 100 largest cities by population, which sort do you think has a better expected worst case runtime in seconds?

1. Counting Sort (as described in our demo)
2. Quicksort

​

​

First question to ask yourself: What is the alphabet for counting sort here?

​

​

Counting Sort vs. Quicksort

For sorting an array of the 100 largest cities by population, which sort do you think has a better expected worst case runtime in seconds?

• Counting Sort (as described in our demo)
• Quicksort

​

​

Counting sort requires building an array of size 37,832,892 (population of Tokyo).

​

​

Counts

...

Counting Sort Runtime Analysis

What is the runtime for counting sort on N keys with alphabet of size R?

• Treat R as a variable, not a constant.

Counting Sort Runtime Analysis

Total runtime on N keys with alphabet of size R: Θ(N+R)

• Creating and filling our count-related arrays: Θ(R)
• Example: R = 4 for four card suits.
• Counting each item and copying into new array: Θ(N)

​

​

​

​

​

Memory usage: Θ(N+R)

​

Bottom line: If N is ≥ R, then we expect reasonable performance.

See hidden slide after this for a more verbose explanation.

Counting Sort Runtime Analysis (More Verbose)

Total runtime on N keys with alphabet of size R: Θ(N+R)

• Create an array of size R to store counts: Θ(R)
• Counting number of each item: Θ(N)
• Calculating target positions of each item: Θ(R)
• Creating an array of size N to store ordered data: Θ(N)
• Copying items from original array to ordered array: Do N times:
• Check target position: Θ(1)
• Update target position: Θ(1)
• Copying items from ordered array back to original array: Θ(N)�

Memory usage: Θ(N+R)

​

Bottom line: If N is ≥ R, then we expect reasonable performance.

Counting Sort vs. Quicksort

Give an example of a specific situation where Counting Sort will be clearly faster than Quicksort.

• Counting Sort: Θ(N+R)
• Quicksort: Θ(N log N)

​

Previous example was sorting N = 100 cities by population (R = 37,832,892).

​

​

Counting Sort vs. Quicksort

Give an example of a specific situation where Counting Sort will be clearly faster than Quicksort.

• Counting Sort: Θ(N+R)
• Quicksort: Θ(N log N)

​

​

​

Sort Summary

Counting sort is nice, but alphabetic restriction limits usefulness.

• Idea: Let’s try digit-by-digit sorting.
• The set of possible digits will be a relatively small alphabet.

N: Number of keys. R: Size of alphabet.

LSD Radix Sort

Lecture 35, CS61B, Spring 2023

Warmup: Digit-by-digit Sorting

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

Radix Sort

Counting sort is slow when the alphabet is large.

• By decomposing input into a string of characters from a finite alphabet, we can force R to be small.

Digit-by-digit Counting Sort

As we’ve seen, we can sort each digit independently from rightmost digit towards left.

• Example: Over {♣, ♠, ♥, ♦}

Digit-by-digit Counting Sort

Sort each digit independently from rightmost digit towards left.

• Example: Over {1, 2, 3, 4}

LSD Radix Sort

Non-comparison based sorting algorithms that proceed digit-by-digit are called “Radix Sorts”.

​

Via wikipedia: “In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers.”

​

The sort we’ve just discussed is called “LSD Radix Sort”.

• LSD: Least Significant Digit.

LSD Runtime

What is the runtime of LSD sort?

• Pick appropriate letters to represent non-constant terms.

LSD Runtime

What is the runtime of LSD sort?

• Θ(WN+WR)
• N: Number of items, R: size of alphabet, W: Width of each item in # digits

Non-equal Key Lengths

After processing least significant digit, we have array shown below. Now what?

​

Non-equal Key Lengths

When keys are of different lengths, can treat empty spaces as less than all other characters.

Sorting Summary

W passes of counting sort: Θ(WN+WR) runtime.

• Annoying feature: Runtime depends on length of longest key.

​

​

N: Number of keys. R: Size of alphabet. W: Width of longest key.

*: Assumes constant compareTo time.

MSD Radix Sort

Lecture 35, CS61B, Spring 2023

Warmup: Digit-by-digit Sorting

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

MSD (Most Significant Digit) Radix Sort

Basic idea: Just like LSD, but sort from leftmost digit towards the right.

MSD Sort Question: http://yellkey.com/ground

Suppose we sort by topmost digit, then middle digit, then rightmost digit. Will we arrive at the correct result? A. Yes, B. No

MSD Sort Question

Suppose we sort by topmost digit, then middle digit, then rightmost digit. Will we arrive at the correct result? A. Yes, B. No. How do we fix?

MSD Radix Sort (correct edition)

Key idea: Sort each subproblem separately.

Runtime of MSD

What is the Best Case of MSD sort (in terms of N, W, R)?

​

What is the Worst Case of MSD sort (in terms of N, W, R)?

Runtime of MSD

Best Case.

• We finish in one counting sort pass, looking only at the top digit: Θ(N + R)

​

Worst Case.

• We have to look at every character, degenerating to LSD sort: Θ(WN + WR)

Sorting Runtime Analysis

​

​

​

N: Number of keys. R: Size of alphabet. W: Width of longest key.

*: Assumes constant compareTo time.

Sounds of Sorting Algorithms

Starts with selection sort: https://www.youtube.com/watch?v=kPRA0W1kECg

Insertion sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=0m9s

Quicksort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=0m38s

Mergesort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m05s

Heapsort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m28s

LSD sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m54s

MSD sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=2m10s

Shell’s sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m37s

Questions to ponder (later… after class):

• How many items are sorted in the video for selection sort?
• Why does insertion sort take longer / more compares than selection sort?
• At what time stamp does the first partition complete for Quicksort?
• Could the size of the input used by mergesort in the video be a power of 2?
• What do the colors mean for heapsort?
• How many characters are in the alphabet used for the LSD sort problem?
• How many digits are in the keys used for the LSD sort problem?

Citations

Creepy eye thing, title slide: http://photos3.meetupstatic.com/photos/event/a/3/f/4/highres_335141972.jpeg

​