Sorting and Efficiency

This week we learnt about different types of sorting algorithm, they are:

Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Merge Sort, and Tim Sort.

Tim Sort:

Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsets of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently. This is done by merging an identified subset, called a run, with existing runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is used to sort arrays of non-primitive type in Java SE 7 on the Android platform and in GNU Octave.

from: http://en.wikipedia.org/wiki/Timsort 

To understand the sorting process and the run time of different sorting method with different type of list, here is a website that can help. It comes with some *.gif files to simulate the process, this more visualize way helps me to understand much more, Hope it helps you as well.





And the graph below shows the efficiency comparison of the Selection Sort, Merge Sort, Intersection Sort [, and Array Sort]


From the Graph one can see that selection sort is the least efficient one compared to the three others. For insertion sort and merge sort, is better to chose Merge Sort for a longer list as it grows more liner than Insertion sort. Overall, Arrays Sort is the best one out of this four types.

When talking about sorting algorithms, we usually look at the best case, worst case and average case. And this bring us to Big O. For example, best case for insertion sort is O(n), average case is O(n**2), and worst case is O(n**2); and other example, best case is O(n log n) for typical and O(n) for natural variant, average case is O(n log n), worst case is O(n log n).

Week 10 - Sorting Algorithm

Start talking about sorting algorithm again...

Remember learning about sorting algorithm in CSC108 last term.
We learnt about:

1. Bubble sort;
• https://www.youtube.com/watch?v=lyZQPjUT5B4
2. Selection sort; and
• https://www.youtube.com/watch?v=Ns4TPTC8whw
3. Insertion sort.
• https://www.youtube.com/watch?v=ROalU379l3U

The links following each of the sorting method is a video that I find fun and interesting to understand the sorting concept.

and now,
we learnt a few new sorting method,

 tim sort, quick sort, merge sort. 

 also learnt that different sorting method have better performance in certain cases but not others, which comes in to the sorting efficiency, which I believe it'll be taught next week.

Three weeks to go!

Well, is close to the end of the school year, and have been learnt a lot about computer science. Class. stack, tree, recursion, list sorting methods and some other things.

I guess Class structure and recursion is what we focused on in this course. Here is a simple example,

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

The two key elements of a recursive algorithm are: 

• The termination condition: n == 0 

• The reduction step where the function calls itself with a smaller number each time:  factorial(n - 1) 

Source: stackoverflow

Recursion required more thinking when designing a program, but it is a "lazier way" of programming. Using recursion, you need to write less lines of code and the whole function will looks much simpler and neat.

There are three great virtues of a programmer

1. Laziness: The quality that makes you go to great effort to reduce overall energy expenditure. It makes you write labor-saving programs that other people will find useful and document what you wrote so you don't have to answer so many questions about it.
2. Impatience: The anger you feel when the computer is being lazy. This makes you write programs that don't just react to your needs, but actually anticipate them. Or at least pretend to.
3. Hubris: The quality that makes you write (and maintain) programs that other people won't want to say bad things about.

 By: Larry Wall, the original author of the Perl programming language

Week 8

Assignment 2

This week is quite busy and packed. We are now working on Assignment 2 Part I. Playing around with the binary tree and LinkedLists. Plus we are doing exercise 3 this week.

Dead Lines of Mid-Terms, Final Essays, and big Assignments of all courses are coming close; hopefully Computer Sciences classes and assignments provides me so fun and relaxing time from these annoying works. 

These slogs are so inspiring and interesting to read, I learnt a lot from them: 

• http://csc148winter2014.wordpress.com/

• http://hepingsheng.wordpress.com/
• http://pythoncodeshark.wordpress.com/