Impression of Week 10

      The key point this week was efficiency.
      I remember we did two things. How to check if an element is in the list efficiently? And how to sort a list efficiently.
      We all agreed that the efficient way to check an element in the list is sort of like checking a binary tree. If the value we are checking is greater than the middle value in the list, check the right half of the list, otherwise check the left. This is an recursive function, we are always checking the middle value in the right or left list until we find the value or reach the end. In this way, we reduce the path from linear to logistic which is a huge step considering a really large list.
      But that function mentioned above need a sorted list which leads to our second problem of sorting a list. We considered the sorting algorithm we already known, bobble, insertion and selection. Although they are slightly different in their running time, but they are all portion to the length of the list squared. So what we can do is to reduce one length of the list into the lg of the length. Here we introduce a function called quick sort.

def quick_sort(L):
    ''' (list) -> list

    Return a new list with the same elements as L in
    ascending order.

    >>> L = []
    >>> quick_sort(L)
    []
    >>> L = [17]
    >>> quick_sort(L)
    [17]
    >>> L = [3, 1, 2]
    >>> quick_sort(L)
    [1, 2, 3]
    '''
    if len(L) < 2:
        # copy of L
        return L[:]
    else:
        return (quick_sort([i for i in L if i < L[0]]) +
                [L[0]] +
                quick_sort([i for i in L[1:] if i >= L[0]]))

      Tracing one example, in each step, this function divides the list into three parts, the first element in the list, the left with all the value less than the first and the right with all the value larger than the first. In each step, we go through all the value, so the number of iteration we are taking is portion to the length of the list. But the number of steps we are taking is nearly portion to lg(length). So the running time of the whole function is portion to length*lg(length). Considering a really large list, this function will save a lot time.