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/

Recursion

Have been talking about recursion from the begging of the semester and we have learnt a lot about recursion already. Recursion is basically calling the function again and again within the same function. Using recursion can help to break a complex problem down into smaller and simpler ones; getting smaller and smaller sub-functions until the problem can be solved.

The most simple problem is to sum up the integers in a nested list, other examples are Tree and LinkedList.

Using recursion really helps to solve "BIG" complex problems.

The Tower of Hanoi!! - week 6

Had fun with the Tower of Hanoi with four pegs ( the Reve's puzzle) these few weeks!!

We wrote a program to move cheeses around in at least four or more stools.

This was a bit challenging but was pretty fun.

This picture shows the begging of the Game.

I also learnt a lot form others' Slogs, they are fun and interesting to read too :)for example:

http://blogsteria.wordpress.com/
http://yyhcsc148.blogspot.ca/


HAHA
Oh! and is reading week, YEAH! Wish everyone have a fantastic reading and do a LOT of READING!!   :P
 

Week 5

More Recursion Function

So in this week, we learnt mare about recursion... Some examples like Tracing Turtle, Nested List, etc. they help me a lot to understand what and how recursion functions work.

Tracing Turtle

In the lab this week, we wrote some recursion functions, mostly about nested list and they are good exercises.

Tower of Hanoi

Oh and I am now "Moving Cheeses" around! Wish me success on that... Tower of Hanoi, HAHA!