For BST, when we are writing the codes, it's important to keep in mind the general structure of BST, which is essential to its amazing efficiency. As long as we understand the logic in there, we can arrive at distinctive cases to consider and thus, carry out the codes. With regards to the delete function, I am still troubled by aliasing problem. If we leave out return_node, and instead, directly return note.right/node.left would results in the wrong outcome. I would appreciate if anyone could explain this to me.
In the meanwhile, we starts on sorting this week. What confused me at first is how we take consideration of the efficiency of sorting since comparison, swapping exists side by side in the code. And the answer is, consider the number of comparisons. I will provide a summary below about the review of sorting algorithm we leant since 108.
Selection sort: the basic idea is the select the smallest item to the front starting at index 0. thus, in the first round, there would be n-1 comparison, n-2,n-2 follows. Add them together, we get a quadratic equation.
Insertion sort: start at the second item, we look at the next item and compare it with the precious one, if smaller, shift forwards, and repeat the steps. As a result, there exist a worst case and a optimal case, corresponding to backwards and already sorted. For the worst case, the number of comparison would be the same as selection, meanwhile, the time for swapping is unneglectable. On the contrary, the optimal case would only require n-1 comparison.
bubble sort: either bubble the smallest to the front or bubble the largest to the end by comparing adjacent items. Thereby, it would take almost the same amount time as selection to come to a sorted list.
Notably, Danny mentioned in class that powers are acceptable, but not exponential.
No comments:
Post a Comment