Week 11 Sorting and efficency

Actually, I try to analyse some kind of sorting during last week slog...For this, its more likely to be a comparison.

The graph above is a brief summary to three sorting method, generally speaking, it seems that the least efficiency should be selection sort... 

According ti the code and example given during the lecture (http://www.cdf.toronto.edu/~heap/148/W14/Lectures/dustin/W10/sort.py), the result is 
Random list generated

Example code in python:
def select(L):
    """Produce copy of L in sorted order by selection sort
    """
    L1 = L[:]
    for i in range(len(L1)):
        m = min(L1[i:])
        j = L1.index(m,i)
        L1[i], L1[j] = L1[j], L1[i]
    return L1

def merge_sort(L):
    """Produce copy of L in non-decreasing order

    >>> merge_sort([1, 5, 3, 4, 2])
    [1, 2, 3, 4, 5]
    """
    if len(L) < 2 :
        return L
    else :
        left_sublist = L[:len(L)//2]
        right_sublist = L[len(L)//2:]
        return merge2(merge_sort(left_sublist), 

                      merge_sort(right_sublist))

 def quick(L):
    if len(L) > 1:
        pivot = L[0] (*)
        smaller_than_pivot = [x for x in L[1:] if x < pivot]
        larger_than_pivot = [x for x in L[1:] if x >= pivot]
        return quick(smaller_than_pivot) + [pivot] + quick(larger_than_pivot)
    else:
        return L


FOR 1000 ITEMS:
0.029001951217651367 - select sort
0.004999876022338867 - quick sort
0.10900616645812988 - quick sort on already-sorted list
0.008000850677490234 - merge sort
0.0010001659393310547 - built-in sort
0.0009999275207519531 - count_sort

This result gives a opposite conclusion...When I try more, the result varies
FOR 1000 ITEMS:
0.030001163482666016 - select sort
0.00400090217590332 - quick sort
0.11100602149963379 - quick sort on already-sorted list
0.009001016616821289 - merge sort
0.0 - built-in sort
0.0009999275207519531 - count_sort


However, if change the * to pivot = L[(len(L)//2)],  the efficiency of quick sort on already-sorted list has improved. This is because when choosing the middle one as the pivot for the sorted list, the elements before pivot are both smaller than pivot, there is no need for recursion.   
FOR 1000 ITEMS:
0.031002044677734375 - select sort
0.005000114440917969 - quick sort
0.00400090217590332 - quick sort on already-sorted list
0.00800013542175293 - merge sort
0.0 - built-in sort

0.0009999275207519531 - count_sort

Quick sort becomes more efficiency. From another website, http://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice

• Quicksort: 2nln(n) comparisons and 13nln(n) swaps on average
• Mergesort: 1.44nln(n) comparisons, but up to 8.66nln(n) array accesses (mergesort is not swap based, so we cannot count that).
• Insertionsort: 14n2 comparisons and 14n2 swaps on average.

It seems that  the type of input can change the efficiency. For example, an input in reverse-sorted order renders the quick sort very inefficient, whereas it may not have as big an impact on other sorts, which was another thing I had never know of from previous experience. In such cases, randomizing the input, or increasing the max-recursion limit can be very important. 

A website found useful: http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf

WEEK N?

 Selection

Selection sort is probably one of the simplest and most intuitive approaches to sorting - you look through the the list (or in this case the deck of cards) to find the smallest element, and put that aside. Then you go through the rest of the deck and continue the process as many times as there were cards you started with and you end up with a sorted deck. In terms of code, a possible implementation is starting at the first (0th) element of an array, and switching it with the smallest value of the rest of the array. Then the second time through you can start on the second (1st) element and so on until you have gone through the array. 

If the size of the input (the number of elements) is n, then the first time through the list you have to check n - 1 elements. The second time, you ignore one element, so you only need to check n - 2 elements, and so on until you have 0 elements to check. So in relation to n, the number of operations you have to do is (n - 1) + (n - 2) + ... + 1 =  (n^2 + n) / 2, which means selection is O(n^2)

Recall from CSC108:

Bubble Sort:

Selection Sort:

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

64 25 12 22 11

11 25 12 22 64

11 12 25 22 64

11 12 22 25 64

11 12 22 25 64

Tree pre_order, in_order

Preorder is 

1. Visit the root.
2. Traverse the left subtree.



Preorder

3. Traverse the right subtree.

Inorder is 

1. Traverse the left subtree.
2. Visit root.



Inorder

3. Traverse the right subtree. 

In python, using recursive to travel around, code is:

def preorder(tl: 'TreeList') -> list:

    

    return [] if tl is None else ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

def inorder(tl: 'TreeList') -> list:

  

    return [] if tl is None else inorder(tl[1]) + [tl[0]] + inorder(tl[2]).

In the exercise 3, we are asked to return the tree according to the preorder list and inorder list given. Accroding to the characteristic of two Tree traversal, it can be known that the first element in preorder is the first root node. Use .find to find the index i for preorder[0] in inorder, inorder[0:i]is the left subclass and inorder[i+1:]is the right subclass. And then the second element in preorder will be another node  ...(using recursion)until all the element has been structed.  

Week 7

Recursion is not intrinsically better or worse than loops - each has advantages and disadvantages, and those even depend on the programming language (and implementation).

In functional programming language implementations, sometimes, for loop can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.

In the past test, this question can be solved by recursion or loop.

def rec_len(L):

    """(nested list) -> int

    Return the total number of non-list elements within nested list L.

    For example, rec_len([1, 'two', [[], [[3]]]]) == 3.

    """

    result = 0

    if isinstance(L,list):

        for item in L:

            result += rec_len(item)

        return result

    else:

        return 1

or 

def rec_len(L):

    """(nested list) -> int

    Return the total number of non-list elements within nested list L.

    For example, rec_len([1, 'two', [[], [[3]]]]) == 3.

    """

   return sum(rec_len(x) if isinstance(x,list) else 1 for x in L)

Recursion is more convince.

Reading week

Review? Maybe

return str.join(s, [nested_join(s, x) if isinstance(x, list) else x for x in L])

Empty Stack: (last in, first out) | | | | | | ------- After Pushing A, you get: | | | | | A | ------- After Pushing B, you get: | | | A | | B | ------- After Popping, you get: | | | | | B | ------- class Stack:     """A last-in, first-out (LIFO) stack of items"""     def __init__(self: 'Stack', data: list =None) -> None:         """Create a new empty Stack using data         data --- initial contents of Stack         """         if data:              self._data = data[:]          else:             self._data = []     def pop(self: 'Stack') -> object:         """Remove and return the top item."""         return self._data.pop()     def is_empty(self: 'Stack') -> bool:         """Return whether the stack is empty."""         return self._data == []     def push(self: 'Stack', obj: object) -> None:         """Place o on top of the stack."""         self._data.append(obj)

Binary tree

There is at most 2 children on each node(left children and right children if exists), the degree of each node can be at most 2. Path is a sequence of nodes n1...nk, where there is an edge from ni to ni+1. The length of a path is the number of
edges in it and there is only a unique path from the root to each node.

Binary tree can be combine with recursion to search value by using either pre-order traversal,in-order traversal or post-order traversal. The difference is the order of meeting the root. And is no cycles -- no path from the loop.

Binary Tree

Week 5?

Recursion is more difficult than I expected. It feels like that recursion is the higher level of loop, more helpful under the complex restriction. We spent the whole lab in the first coding question but still not able to solve it out. Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. And, it is said that often, a problem is easier expressed using recursion. This is especially true when you talk about tree-like data structures (e.g. directories, decision trees...).These data structures are finite in nature, so most of the time processing them is clearer with recursion.When stack-depth is often limited, and every function call requires a piece of stack, and when talking about a possibly infinite data structure you will have to abandon recursion and translate it into iteration.Especially functional languages are good at handling 'infinite' recursion. Imperative languages are focused on iteration-like loops. Hope I can handle it in the assignment...