To talk briefly about A2...
Assignment #2 was due during this week, so that had taken up a significant amount of my free time. I thought the assignment was a relatively straight forward project that wasn't extremely difficult, and I'm pretty sure most people thought it was an relatively easy assignment. Looking forward to get my marks back for this project. Guess all that's left at this point is just preparing for T2 test and the finals. How did everyone else feel about A2? Did you think it was a hard/easy project? Leave your thoughts on the comment section below (please)!
Moving on to this week in lecture...
In this week's lecture, we talked about the big-Oh notation of some popular sorting algorithms, specifically with references to quick sort and merge sort. Among the sorting algorithms that we have gone through in the past week, quick sort and merge sort are the only ones that have O(n log n) in average case, versus the poor performance of sorting methods such as bubble sort and selection sort which have O(n^2).
Sun Tzu said: Divide and Conquer!
Quick sort and merge sort are interesting because both utilize a divide and conquer strategy to achieve optimum efficiency. For those who have never heard of the term divide and conquer, in the case of programming, divide and conquer strategies break a problem down in smaller problems, such that the problem as a whole becomes easier to solve. For example, merge sort works by repeated dividing a list into small sub-lists until every sublist is of length 2 or smaller, at which point each sublist is then sorted and repeated merged together, until a sorted list is created (see image below).
Final thoughts for the day...
As usual, what are everyone else's thoughts on the different sorting algorithms seen in lecture and lab? Which one do you think is the best? Do YOU know of an even quicker way to sort a list? Please let me know in the comments section below!
In the meanwhile,
Cheers
Image Cite:
Merge Sort. Digital image. N.p., n.d. Web. 4 Apr. 2014. <http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/Gifs/mergeSort.gif>.
In this week's lecture, we talked about the big-Oh notation of some popular sorting algorithms, specifically with references to quick sort and merge sort. Among the sorting algorithms that we have gone through in the past week, quick sort and merge sort are the only ones that have O(n log n) in average case, versus the poor performance of sorting methods such as bubble sort and selection sort which have O(n^2).
Sun Tzu said: Divide and Conquer!
Quick sort and merge sort are interesting because both utilize a divide and conquer strategy to achieve optimum efficiency. For those who have never heard of the term divide and conquer, in the case of programming, divide and conquer strategies break a problem down in smaller problems, such that the problem as a whole becomes easier to solve. For example, merge sort works by repeated dividing a list into small sub-lists until every sublist is of length 2 or smaller, at which point each sublist is then sorted and repeated merged together, until a sorted list is created (see image below).
Merge sort in action
Final thoughts for the day...
As usual, what are everyone else's thoughts on the different sorting algorithms seen in lecture and lab? Which one do you think is the best? Do YOU know of an even quicker way to sort a list? Please let me know in the comments section below!
In the meanwhile,
Cheers
Image Cite:
Merge Sort. Digital image. N.p., n.d. Web. 4 Apr. 2014. <http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/Gifs/mergeSort.gif>.
No comments:
Post a Comment