This document contains the instructions for the week 9 CSC148H lab. To earn your lab mark, you must actively participate in the lab. We mark you in order to ensure a serious attempt at learning, not to make careful critical judgments on your work.
In lecture, we will shortly be considering some advanced sorting methods, particularly quicksort and merge sort. This lab has you implement the Radix Sort algorithm using Queues, and write a set of nose tests. (Based on Exercise 8 on page 96 of the course textbook.)
Pick a partner.
You will implement a radix sort for base 10 numbers. A radix sort for base 10 integers is a mechanical sorting technique that utilizes a collection of bins: one main bin and 10 digit bins. Each bin is a queue. The algorithm follows these steps:
Place each number in the main bin.
Remove each value in the main bin and place it in a digit bin corresponding to the digit being considered, starting with the least significant digit.
Once all the values are placed in the appropriate digit bin, collect the values from bin 0 to bin 9, in order, and place them back in the the main bin.
Continue the process (steps 2. and 3.) with the tens digit, the hundreds digit, and so on. After the last digit is processed, the main bin contains the values in order.
For example, let's say we have a list that contains the following integers:
|
240 |
28 |
5 |
18 |
140 |
2 |
Your radix sort will place all six numbers in the main bin.
Next, consider the 1's digit for each number in the main bin and place it in its corresponding digit bin. For example, after the first pass, the digit bins will look like this:
|
0-bin |
1-bin |
2-bin |
3-bin |
4-bin |
5-bin |
6-bin |
7-bin |
8-bin |
9-bin |
|
240 140 |
|
2 |
|
|
5 |
|
|
28 18 |
|
Now, in order, place these integers back into the main bin. The main bin now looks like this:
|
240 |
140 |
2 |
5 |
28 |
18 |
Next, consider the 10's digit for each number (in order) and place it in its corresponding digit bin. For example, after this second pass the digit bins will look like this:
|
0-bin |
1-bin |
2-bin |
3-bin |
4-bin |
5-bin |
6-bin |
7-bin |
8-bin |
9-bin |
|
2 5 |
18 |
28 |
|
240 140 |
|
|
|
|
|
Now, in order, we place these integers back into the main bin. The main bin now looks like this:
|
2 |
5 |
18 |
28 |
240 |
140 |
Next, we consider the 100's digit for each number (in order) and place it in its corresponding digit bin. For example, after this pass the digit bin will look like this:
|
0-bin |
1-bin |
2-bin |
3-bin |
4-bin |
5-bin |
6-bin |
7-bin |
8-bin |
9-bin |
|
2 5 18 28 |
140 |
240 |
|
|
|
|
|
|
|
Now, in order, we place these integers back into the main bin. The main bin now looks like this:
|
2 |
5 |
18 |
28 |
140 |
240 |
If we tried the 1000's digit we would find that all the numbers would go into the 0-bin. We are done and the list is sorted.
Your task is to define a non-recursive function radix_sort that takes a list of integers and returns the same list of integers in sorted order using the radix sort algorithm. Remember, the bins used in the sorting algorithm should be Queues. You can get the queue.py file here. After you implement radix_sort, write a good set of nose tests for it. To perform this testing, you should begin by writing a function that takes a list as input, and determines whether the list is sorted. The radix sorting procedure you implemented sorts a list in non-decreasing order; in other words, each element is no greater than the element to its right. You should test your radix sort procedure to ensure that each result is indeed sorted in non-decreasing order, and that the result contains exactly those elements from the input list.