There are many kinds of sorting algorithm. And what I want to talk here is about there efficiency and why it has such efficiency.
Firstly, among those sorting algorithms, there are two kind of sort. One is comparison sort and another is non-comparison sort. Comparison sort means that we have to compare the item we get with another item, then we can decide where to put this item in the list. However, as for efficiency aspect, the time complexity of the most efficient comparison sort must bigger than O(n). Because we have to access to every element in the list otherwise we can no compare it with others. So if we want to compare we have to get the item's value and then the time complexity must be bigger than O(n). Non-comparison sort can have O(n) time complexity but it will demand more space to store the data.
The most intuitive algorithms of sorting might be the insertion sort. Given 1 0 4 2 as the input list, the way we think is just the process of insertion sort. We first put 0 to the front of 1 and then we find 2 is smaller than 4 but bigger than 1 then we put 2 between these two numbers. We compare the number and we put it in the right place. The time complexity of insertion sort is O(n^2). Because we have to compare the item we get in our hand with each item in front of the current item.
Selection sort is quiet simple as well. It select the first smallest item in the list and put it on the first place in the list,(or the last one, depends on the list is descending or ascending). And then the second smallest one should be put on the second place in the list. The time complexity of this algorithm is O(n^2) as well, for we have to compare the item we got with all other items.
Then here we come the QuickSort and MergeSort. These two has really good sorting algorithms. The average runtimes are all O(nlogn). Both of them are recursive.
Why they have O(nlogn) time complexity?
We can solve this buy drawing a tree.
Take MergeSort for an example
n ------ need n step to merge
n/2 n/2 ------ each item need n/2 to merge, sum is 2*n/2 = n
n/4 n/4 n/4 n/4 ------ each item need n/4 to merge, sum is 4*n/4 = n
.......
As we can see in the above tree, each depth of the tree need n step to complete its task. Then the sum of all is nlogn because depth of the tree we can have is at most logn.
The non-comparison sorts are really interesting. But I still don't understand many of them.
Sunday, March 30, 2014
Sunday, March 2, 2014
More Talk About Recursion!
From the beginning of the csc148 class, we have already been told the importance of recursion. Knowing recursion and analyzing recursion is a important step in programming. However, recursion in the most time is extremely hard to track all the stuff. And I want to show some ways to fully understand the recursion and my experience about learning the recursion.
First of all, one powerful tool to understand recursion is drawing the recursion tree. (Actually I learn this stuff from a book called Introduction of Algorithms,And this is an extremely good book that tells you everything you need about understanding algorithm) A recursion tree is just like the picture the professor draw during the lecture. Take the hanoi tower as an example, the top node is the root of the tree and also the first time we call the method. Then the tree will be constantly adding the left nodes until it meet the base case, which means there are only one cheese left and it will execute the first step.Then the left most node will quit and you will get into the right node of the previous left node. That's sort of how I figure out the recursion in a tree model.
Another tool I guess is the visualizer. And actually it will give you more understanding about how computer works. For example, after visualizing one simple recursion function, you may notice that the recursion is actually based on the stack ADT. That's why when we sometimes forget to write the base case for the recursion, we will get stack overflow error.
My advice about learning and understanding the recursion is that don't rush and work step by step. The recursion is actually simple and it is so similar to one proof method in math, which is the Proof by Induction. I find it helpful if you can completely understand the Induction first.
First of all, one powerful tool to understand recursion is drawing the recursion tree. (Actually I learn this stuff from a book called Introduction of Algorithms,And this is an extremely good book that tells you everything you need about understanding algorithm) A recursion tree is just like the picture the professor draw during the lecture. Take the hanoi tower as an example, the top node is the root of the tree and also the first time we call the method. Then the tree will be constantly adding the left nodes until it meet the base case, which means there are only one cheese left and it will execute the first step.Then the left most node will quit and you will get into the right node of the previous left node. That's sort of how I figure out the recursion in a tree model.
Another tool I guess is the visualizer. And actually it will give you more understanding about how computer works. For example, after visualizing one simple recursion function, you may notice that the recursion is actually based on the stack ADT. That's why when we sometimes forget to write the base case for the recursion, we will get stack overflow error.
My advice about learning and understanding the recursion is that don't rush and work step by step. The recursion is actually simple and it is so similar to one proof method in math, which is the Proof by Induction. I find it helpful if you can completely understand the Induction first.
Subscribe to:
Posts (Atom)