This week is quite busy. Assignment 2 is
really challenging. The hints given by professor in the lecture are really
helpful for us when solving assignment. Basically, this assignment is about
recursion. We need to consider every base case carefully and connect them
together. After we had an idea of how to divide the problem into several cases,
writing the code became much easier.
Another thing we learned this week is
sorting. Quick sort and merge sort were taught in class. Quick sort works by
somehow choosing a pivot and breaking a list into two sublists (everything
smaller than the pivot, everything larger the pivot). It continues to break
down the list in this way until the list can't be broken down and brings all
the sublists together. Its efficiency is O(n log n). Since it takes around
log(n) steps to break down the list and each step has (n + constant)
comparisons. However, in rare cases if we keep choosing the greatest or least
element, the efficiency will be reduced to O(n^2). One way to avoid that is to
find the first, last and middle elements of the list and choose the median as
the pivot. Merge sort is kind of like quick sort however we need to add a help
function for this sort. Merge works by dividing the list in half until it can't
be divided any more, and then mergesorting each of the two halves. The
efficiency of merge sort is stable compared to quick sort which is also O(n log
n). Since we don't need to choose the pivot for merge sort, the efficiency of
merge sort doesn't depend on the order of elements in the list but only the
number of elements in the list.
I feel the algorithm is a little bit vague
since we didn't do an accurate derivation however obviously the efficiency of
merge sort and quick sort is much quicker than selection sort which is O(n^2).
Thus, practically we use quick sort and merge sort to sort a large-size list.
I didn't consider efficiency in solving
problems until this week's lecture. It's quite important to know something
about efficiency.
No comments:
Post a Comment