Reading
Read the algorithms section of http://www.dangermouse.net/esoteric/
Take a look at http://www.sorting-algorithms.com/
Reading Questions:
1. What is the improvement of LenPEG 2 over LenPEG
(In LenPEG 2, the image of Lenna is compressed to an empty file, rather than a file containing 0)
2. What is the average compression of LenPEG 2
Infinite, since one image has infinite compression ratio
3. Why is the best case for any (implementable) sorting algorithm at least O(n)
Because every item must be checked to see that the list is in order
4. What is dropsort?
Dropsort is a sorting algorithm that involves discarding any items in a list that are out of order, leaving a sorted (though incomplete) list
Homework:
You will be implementing a recursive version of dropsort that retains all of its data.
Steps to take (read the entire assignment before starting the homework):
Implement a doubly linked list class in Python (in a doubly linked list, each node "knows about" the previous node in the list and the next node in the list, making it iterable in both directions). Your doubly linked list need not have every functionality under the sun, only those required for the rest of this homework.
Write a function that takes in a doubly linked list and recursively performs dropsort on it. However, instead of deleting an unsorted value from the list, move the node to a new list and perform dropsort on that (you remember recursion, don't you?). This function should return a list of doubly linked lists that are in order. This return value can be a regular python list if you want.
Write a function that takes in a list of doubly linked lists in order and merges them into one sorted list by iterating through the first item in each doubly linked list and adding the lowest value to the merged list until eventually there is one sorted list.
Write a function that combines these two and performs recursive dropsort!
Quiz question(s):
Come up with your own stupid algorithm. The funnier the better!
The metasort: gather a group of friends and have a deep conversation about why the list really needs to be sorted. After all, in its current state, the list is in a beautiful pattern in its own way.
Why is a doubly linked list a good choice of a data structure for the recursive dropsort that you implemented?
If the list is not sorted, other lists have to be created. With a doubly linked list, nodes can be moved from one list to another with no additional memory required. This is particularly useful in the worst case scenario, where n lists must be created. Singly linked lists will accomplish the same thing, but it's easier to remove nodes if each node knows where the previous node in the list is.