Suggested Topics
Sorting Algorithms
Selection Sort:
Selection sort finds the minimum item in the list, and then swaps it with the first item. It then selection sorts the rest of the list, excluding the 0th element, which is already in order.
Selection sort is what I feel might be the approach of a first year Computer Science student if asked to write a sorting algorithm, provided they had never heard of a sorting algorithm. The naive idea of grabbing the min over and over again until you have a sorted list is very intuitive, although, it turns out, very inefficient. You have to do n passes through the list, and a swap each time. This makes a total of n + n-1 + ... + 1 comparisons, which equals n^2 - n and puts the algorithm in O(n^2). Although slow, it doesn't use a lot of memory, doesn't require you to subdivide the list into a billion pieces, and doesn't require a ton of recursive calls. It has a kind of beautiful, naive simplicity. I wrote my own sort that relies on the builtin min AND max to improve on selection sort slightly by reducing the number of passes through the list. If I knew of a function that could simultaneously find the min, return it, and remove it from the list (a sort of min_pop), it would be much faster indeed.
def min_and_max_sort(L):
L1 = L[:]
if len(L1) < 2:
return L1
else:
K1, K2 = [], []
if len(L1)%2 == 1:
j = min(L1)
K1.append(j)
L1.remove(j)
while L1 != []:
j = min(L1)
K1.append(j)
L1.remove(j)
k = max(L1)
K2.append(k)
L1.remove(k)
K2.reverse()
return K1 + K2
Quick Sort:
Quick sort selects a pivot element, and places it in the middle of two new created lists. The one on the left is the list of all elements less than the pivot element, the one on the right is the list of all elements greater than the pivot. The algorithm then quick sorts both of the new lists. On average, quick sort is in O(nlogn), since the pivot process divides the list roughly in half (the log2n component of the runtime), making 1 pass through the list that takes n comparisons with the pivot (the n). It does this until the list is sorted. The simplest quick sort uses the [0] element of the list as a pivot. A problem arises when this simple quick sort is called on an already sorted list. Then, the left list is empty, and the right list contains all the elements except the pivot. Quick sort ends up running n + n-1 + ... + 1 comparisons, putting it in O(n^2). This problem can be circumvented by choosing the pivot at (pseudo)random. Thus, the odds of picking the worst possible pivot (the min or max of the list) are low.
Intuitively, one would expect that quick sort is the fastest of all known sorting algorithms, because it has quick in the name. I was appalled to discover that this is not in fact the case. By far the best part of learning this algorithm was Prof. Heap's one line, recursive, list comprehension implementation of it. My sense of code aesthetic has pretty much only been shaped by Prof. Heap and this course. That said, in my mind, the best of all possible code is recursive, one line, and involves a list comprehension. It is practically self-documenting, and makes very clear that the nature of the solution to the problem involves solving smaller instances of the same problem.The random pivot implementation is especially clever, and I think makes use of all of what is good about my random sorting algorithm (Slog 11), the use (pseudo)randomness. Because I think life seems random to humans, because of our limited sensory and intellectual faculties. Thus, the idea of randomness is very intuitive to us. For example, when we roll a die, it seems that the result is random, but the roll is already completely determined by the physical factors going into the roll (up to randomness at the quantum level). If one had perfect knowledge of all the initial conditions, one could compute the roll. One might need a supercomputer for that, but that is what computer science is for.
Merge Sort:
Merge sort divides the list in half until it is broken up into lists of length 1. It then 'merges' adjacent lists, by adding them such that the resultant list is sorted. It merges by looking at the first element of each of the two sorted component lists being merged, and adding the lesser element to a new list. It does this until both of the old lists are empty, the new list is sorted. It runs in O(nlogn) since it divides the list in half several times so that it does not have to make n^2 comparisons, as it is only comparing the first element of 2 lists, rather than passing through one list over and over again.
Merge sort is the ultimate divide and conquer algorithm. Again there is a very neat and tidy recursive list comprehension implementation, because the solution is indeed to divide the problem up into smaller problems (indeed, list of length 1 sized problems). In the assigned reading, ALL of the algorithms were implemented iteratively, and they were hideous. Good god. Something that complicated is firstly completely unreadable except with a Herculean (Solomonian?) effort, and secondly is more vulnerable to human error, as complexity increases the likelihood of mistake. In this way, solving a recursive problem recursively is far more intuitive, even if the mind cannot follow make sense of stepping through the program as it makes 1000 recursive calls.
Efficiency:
I have reflected on the efficiency of the sorting algorithms under their entry. The general concept of efficiency is one that is useful to Computer Science. It is somewhat satisfying to write code that 'works' or 'gets the job done', but it is far more satisfying to know that you've written code that solves the problem well. This concept of 'well' is based partly on readability, but also largely on efficiency. It makes the difference between doing a job and doing a good job, and requires an intimate knowledge of how your program actually works. It also forces considerable visualization of what the machine is doing as it runs your code. These are educative things, and promotes a level of code-consciousness and revision for optimization that I think are useful in any task. It is the same as editing an essay, or a mathematical proof. Without destroying the ideas, you want to make them clearer, and to communicate them with less effort or words (more efficiently). This detail orientation and desire to improve the utilitarian and aesthetic value of your work are part of what makes the works of man so excellent. Does a chimpanzee care about the beauty of the stick it uses to get ants out of the anthill?
Funny efficiency story, I wrote my own Fibonacci(n) function about a year ago. I wanted to take CSC240, Enriched Introduction to the Theory of Computer Science, but I didn't have the 148 prerequisite or corequisite at the time. When I emailed the Prof about it, she said that the most important thing carried forward from 148 into 240 was recursion. She said as long as I could demonstrate that I understood recursion, I could take the course. So what I did, I talked to my computer programming father about it, and he explained the idea. I did some independent research, and the I wrote my own Fibonacci(n), much like the naive version we looked at first in class.
Looking back with hindsight, it's obvious that I had no concept of efficiency, or caching for speedy storage to prevent redundant function calls. And this must have been obvious to Professor Ellen as well. Much like Python, though, she decided to let me take the course, thus giving me enough rope with which to hang myself. I ended up dropping the course after it seemed too scary from the first couple of weeks. I decided to take 148 first, and here I am, signed up to take 240 next semester. Hopefully it goes better this time. Hopefully.
There was another issue at play too, besides my own lack of desire for an overdifficult challenge. There was a Russian Literature course in the same slot, and it seemed way too good to miss. So I took that instead, and I have no regrets. It was amazing course with an amazing Professor, and I learned a ton about literary analysis. And Russia! Maybe there's a course on Nabokov I can take next semester instead of 240...
So the memoized Fibonacci was interesting on a personal level as well as an intellectual one. Again, excellent techniques I learned from Prof. Heap that I can easily imagine using at some point in the future.
No comments:
Post a Comment