$ mkdir ~/cs170/labs/lab15 $ cd ~/cs170/labs/lab15
One thing that we have mentioned back in CPSC120 was how we can represent colors for images. Thinking back to when we did steganography, we saw that pixels can have colors specified as RGB values. However, we haven't seen how we can specify such colors for Tkinter. Today, before we get started, I'll demonstrate the quick mechanism to convert a tuple of integers into a string that tkinter will understand as a color.
There are A TON of different sorting algorithms. However, as discussed previously, the best generic sorting algorithms can run no better than \(O(n log(n))\). However, that assumes we are trying to sort arbitrary data. . Radix sort is one such algorithm, which only works when sorting integers
In a file called radix.py, create a function
called radix_sort(a_list, digit). This function takes
a list of integers to be sorted, as well as an integer specifying
which digit is being used to sort the list of numbers in this
iteration. This function should return a list of integers, the
sorted integers from the a_list parameter.
The digit integer will be used to determine which digit is being sorted. The least significant digit is specified by a 0 in the digit parameter. To sort a list of numbers, you need to know how many digits are in the largest number of the list. If this is set incorrectly, you will still end up with a "sorted" list, but it will not be sorted by the largest digits.
Radix sort begins by creating a list of 10 empty lists: one for each possible digit value. Then, the algorithm iterates over the integers of a_list placing each integer into the list associated with the value of its digit. Then, each one of those new list of numbers is sorted recursively, on the next digit specified. This continues until you end with an empty list, or you are out of digits to sort.
>>> my_list = [19, 28, 17, 60, 66, 42, 31, 12], >>> radix_return = radix_sort(my_list, 1) >>> print(radix_return) [12, 17, 19, 28, 31, 42, 60, 66] >>> radix_return = radix_sort(my_list, 0) >>> print(radix_return) [60, 31, 42, 12, 66, 17, 28, 19] >>> my_list = [19, 28, 17, 60, 66, 42, 9001, 12] >>> radix_return = radix_sort(my_list, 3) >>> print(radix_return) [12, 17, 19, 28, 42, 60, 66, 9001]
You will have two conditions in your base case: If the parameter list is empty, or the digit being sorted is less than 0, you just return the parameter list.
In your recursive case, you need to create a 2-dimensional list of lists. Use a for loop to initialize this.
You need to be able to get the value of a specific digit from a number to perform this sort. The easiest mechanism for this is using integer division, and modding. Divide each number by \(10 ^ {digit}\), and then mod by 10.
You can combine two lists using the plus operator. After you recursively sort a list, you should combine that returned list with the list you are returning.
When you have finished, create a tar file of your
lab15
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab15.tgz lab15/
To submit your activity, go to inquire.roanoke.edu. You should
see an available assignment called Lab Assignment 15.
Make sure you include a header listing the authors of the file.