[ o,r,S,n,g,i,t]--->Sorting and Efficiency

Sorting reminds me of the last two week’s lectures. Sorting and efficiency are things we spend a long time to talk about in this period of time. I would like to begin form ask myself, what actually the sorting is and how can a sorting algorithm said to be efficient.

This is the definition of sorting on Wikipedia.

Sorting is any process of arranging items according to a certain sequence or in different sets, and therefore, it has two common, yet distinct meanings:   

1. ordering: arranging items of the same kind, class or nature, in some ordered sequence, 

2.categorizing: grouping and labeling items with similar properties together (by sorts).

To make it clear. Using my picture as an example of sorting.

You can see that my photos are listed in random and now I want to sort them into the order by age.

The result shown as follow

For example, we can sort a list of integer from great to small or from small to great or sort some apples form big size to small size. Those actions are all sorting objects. Like we can call the python built-in method sort() to sort number and letters.

>>>a = [3,4,6,1,8,0]

>>>a.sort()

>>>a

[0, 1, 3, 4, 6, 8]

>>>b = ['g','e','w','s']

>>> b.sort()

>>>b

['e', 'g', 's', 'w']

However, u can see that is method is only can sort specific things in specific order. Therefore, we need other method and algorithm to help us sort things we want in orders we want. Like selection sort, insertion sort and bubble sort and so on. Each sorting algorithm has their own way to sort objects and they may run different times to sort same object. Some algorithms good at sorting specific objects. 

For example, to sort [54,26,93,17,77,31,44,55,20] 

merge sort uses 297 steps

insertion sort uses 106 steps

gapinsertion sort uses 181 steps

selection sort uses 132 steps

bubble sort use 154 steps

Therefore, you can find there is a such big difference between those sorting algorithms for their efficiency.

Yes, EFFICIENCY. Now I would like to talk about that. For us, to decide using an algorithm to sort different objects depends on the efficiency. In that case, we need to know, when there are more and more objects contained in the list we sort, how the runtime grows according to the way each sorting method use to sort. To analysis the growing of runtime, we introduce Big-oh.

What is big O?

Big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.Big O notation is used to classify algorithms by how they respond to changes in input size.

For example, for 1<a<b, n^a in O(n^b), or a^n in O(a^b). These are sample examples.

To see a little bit complex example.Lets say that the function is T(n)

max=0                              1

for i in range(0,n):               2

    for j in range(i,n):           3

        sum = 0                    4

        for k in range(i,j):       5

            sum = sum+L[k]         6

        if sum > max:              7

            sum = max              8

We can say that T(n) is O(n^3)

The reasons are listed as follow.

Line 6 takes 1 step

The loop on lines 5-6 iterates at most n times, because i is from 0 to n-1 and j is from i to n-1, so the number of steps is less than n

Lines 4-8 add at most 4 steps.

However, the loop on 3-8 iterates at most n times and 2-8 iterates exactly n times.

line 1 add 1 step.

Therefore, the number of steps is <=2n^3+1 <=2n^3+n^3 <=3n^3 for n greater than 1

In the lab, we also ran some different functions and changed the size of input and then filled the chart to get the graph of the growing of each function. Next compared them to get the result in order to observe the change of the runtimes.

Sorting and Efficiency are really important in computer science. Not only because they can help us to solve problems easily, but also because they can help us to improve the efficiency of our program and function.

These are my understanding of Sorting and Efficiency. Hope I can learn more about it and have better understanding of it compare to now I have.  

Working on term test!!!

Hey, there is a term test THIS WEEK!!! In three days!!!

Unbelievable???

But you have to prepare for that!

Hence, in this slog, I want to talk about my preparation on my term test 2.
My result for term test1 is really really bad. That makes me fell upset for a long time. Therefore, I have to try my best at this time.

First, I reviewed all the slides to check that whether I already understand all the things we learned in the lectures.

Second, I plan to read the code I wrote during the lab because that is the things we put the idea into practice. 

Third, I need to rewrite the exercise, cuz you know, sometimes people can forget things they did before by their own.

And then, after those preparations, I can do some past tests to check if I can solve all the problems on it.

Finally, it is better for me to write something bother me or something confuse me, and something need to spend lots of time to remember. Also, something easy for me to forget when I am nervous.


OK~~~I m going to work on the test. Good luck to you guys and me ~~~

Another typical week.(Talk about exercise)

In this week, I think one of the challenges on computer science for me is the exercise 3. In previous weeks' lecture, we've learned a lot of things about the traversal of tree.
There are three ways for us to traverse the trees.
1.Pre-order
2.In-order
3.Post-order

As you can see, the order or the way for these three algorithm to traverse trees are different with each others.

Pre-order

Visit the root.

Traverse the left subtree.

Traverse the right subtree.

In-order 

Traverse the left subtree.

Visit root.

Traverse the right subtree.

Post-order

Traverse the left subtree.

Traverse the right subtree.

Visit the root.

For me, I can easily traverse a tree with these algorithms. However, what make me confusing is to build a tree with given pre-order and in-order.

To solve this problem,I use the given example form the handout to draw picture and find the way to solve that.Let me explain.

[10, 6, 8, 12, 11, 15] (pre-order) 

[8, 6, 12, 10, 11, 15] (in-order)

As we already know, the order for pre-order to traverse is root-->left--->right(which shown above). Therefore, the first item(pre-order[0]) must be the root for the tree which is 10.

Then, the order for in-order to traverse is left-->root-->right. Therefore, items before 10 is the left subtree and items after 10 is the right subtree.

After that, things all become clear. 6 must be the root for the left subtree and use 6 into in-order list to split the left subtree and right subtree for the left subtree.Using this idea to keep traverse in recursive way. Finally we can get the result.

The tree will be:

[10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]

_______________________________________________________________________

Just post my code here after the due day to let everyone see my slog can have an idea about this exercise if you did not do well on it.

def make_tree(preorder, inorder):
    """
    >>> make_tree([10, 6, 8, 12, 11, 15], [8, 6, 12, 10, 11, 15])
    [10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]
    """
    
    if not preorder or not inorder:
        return None
    root = preorder[0]
    in_left = inorder[:inorder.index(root)]
    in_right = inorder[inorder.index(root) + 1:]
    pre_left = preorder[1:len(in_left) + 1]
    pre_right = preorder[len(in_left) + 1:]
    left_sub = make_tree(pre_left, in_left)
    right_sub = make_tree(pre_right, in_right)
    return [root, left_sub, right_sub]







See you in the next slog soon~~~~

Typical week. (talk about assignment2 and lab)

This is a typical week for studying computer science. In this week, we learned something about linked lists and do the work across the same topic in the lab. However, what I want to talk more in this week’s slog is my assignment two.

 

I just finished my assignment two with my partner this weekend. This assignment is about the tree. At first, we designed to use only one class that contains all the requirements in the handout. The reason for this is that we can write less code. In other aspect, in some way one class does meet the requirement. Therefore, this weekend, I and my partner met up and changed our one class to many classes. Those classes including star tree class, bar tree class and so on. It is not hard to fix, but we think our solution works will still and uploaded our first solution with our new solution with many sub-classes. And in this assignment, I also learned how to set common property. That is really helps a lot.

In this week’s lab, I find that in lots of questions, it will be much easier to use list comprehension than the for loop. I am really not good at using list comprehension. Hence I need more practice during the lab and by myself in free time.