$ mkdir ~/cs170/labs/lab25 $ cd ~/cs170/labs/lab25
On Monday, you got to see your test scores. Today, we are going to go through the test IN DETAIL. A majority of you found the coding questions to be unfair, so I want to go over why I felt like they were fair.
One thing that you all need to keep in mind is that while you tend
to joke around a lot during the lab, everything that we cover in
this class is important
This seemed to cause a lot of confusion, so today we will go over it, again in detail. Let's make sure we ALL understand it today before we move on.
One thing that I think all of you could benefit from is actually working problems out on paper before you begin coding at all. I've suggested that to a lot of you, but none of you have really taken that idea to heart. Today you are not allowed to touch a computer until you have fully written a solution out on paper and you have traced your program with the test case provided below.
We have discussed a handful of general sorting techniques up to this point. However, there are a couple of sorting techniques that only work on certain classes of data. For example, requires knowledge of the range of data. Another type of sort is called Radix sort, which can only sort integers. What is really interesting about radix sort is that it is one of the few non-comparison based integer sorting techniques.
Create a function radix_sort(a_list),
which takes a list of . These
strings are going to represent integer numbers, where the strings are
padded with 0's. For example, if the number "1000" is in a_list, the
number 23 is represented as "0023". This function should return a
sorted version of a_list.
In radix sort, all of the are placed in a queue based on the order they are encountered. The queue they are placed in is based on the digits place being examined. You will start from the least significant bit (the right most digit in the string), and place it into the appropriate queue based on that number. For example, for the first iteration of radix sort, the number "064" would be placed in a queue for the the digit '4', while the number "101" would be placed in the queue for the digit '1'.
After you have enqueued all of the items from the original list into the queues, you sequentially dequeue all of the queues in increasing order back into the main list. You then repeat this process for the next digit in the string, until you run out of digits. The resulting list will be a sorted copy of the list.
When you have this written out, make sure you think about the Big-Oh class of radix sort. Write your Big-Oh estimate in a comment in your radix.py file.
>>> print(radix_sort(["0001", "2030", "0122", "0002", "1203", "0333"])) ['0001', '0002', '0122', '0333', '1203', '2030']
For radix sort, you will want to create a list of 10 queues, one for each digit. All of these queues will start off empty. You could use a dictionary, but since you know the strings you have represent integers your sort will be faster if you use just a list.
Remember, Strings are simply a special form of a list. You can
get a specific character from the string using the
[] operator, just like you would on a list. You
can even specify negative values, which might make your code a
little easier to write.
When you have put all of the values into the queues, you need to iterate over your list of queues, dequeueing them until they are empty. You will place the dequeued values into a list, so that you can process the next digits of them.
The above definition of Radix sort is really Least Significant Digit Radix Sort. The other type of Radix sort is Most Significant Digit (MSD) Radix sort, which can be used to sort strings. This function doesn't use a queue, instead it uses recursion!
Write a function
msd_radix_sort(a_list, current_index),
which takes a list of strings as input, and
an integer representing the current digit being explored. These
strings will be only lowercase, alphabetic strings. Your function
should return a sorted copy of the input a_list.
MSD Radix sort places the input lists into buckets, then recursively sorts those buckets using the next character of the strings. Then, you just concatenate the lists back together to get the sorted version of the list.
When you have finished, create a tar file of your
lab25 directory. To create a tar
file, execute the following commands:
cd ~/cs170/labs tar czvf lab25.tgz lab25/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
25. Make sure you include a header
listing the authors of the file.