Week 11 Sorting and Effectiency

    During this week's lecture , Danny has introduced us two extra sorting algorithm ——merge sort and quick sort. The idea of quick sort is to select an item out of the data as a pivot(most of algorithm picks the first item). Then partition the data/list into two halves: items that are less than the pivot and the items that are greater than the pivot . than we can rearrange the list to get the right position of the pivot item we selected , select a new pivot and repeat the partition after that . This is the basic idea of a quick sort. it is a  fairly fast sorting technique. The best case run time for quick sort is O(n). and the worst case is O(nlogn). this is also one interesting idea pops up during the Wednesdays lecture. Since we know what the worst case of quick sort looks like. we can edit/ change our algorithm to avoid such situation by instead of choosing the first item on the list as pivot, now we  randomly pick out pivot item .
    The second sort technique that has been introduced is merge sort . it  splits the list in two halves and sorts two halves individually then merge two sorted halves. merge sort seems like it taking a lot steps to sort a small sized list. However , in a lag sized list . it performs just fine the worst case is same as quick sort O（nlogn)

Week 7 recursion

    Through the past couple weeks we have been study on Recursion, which is basically to repeat a recursive procedure  multiple times. The idea that have been introduced to the class was to repetitively call a recursive function until  a "base case" is reached .
    for example , compute a factorial function would be look like :
def factorial(n):

    if n == 1:
        return 1
    else: 

return n * factorial(n-1)
http://www.python-course.eu/recursive_functions.php [source]

 the program itself is simple. only 5 lines of code .  However, it is really clear that we repetitively call upon the function itself with (n-1) as argument and n*factorial(n-1) as accumulated/final output .

 if n == 1:
        return 1

   this if statement is the base case i called about . with out this piece of code the value of n will keep reduce and function will stuck in to a infinite loop.
 
    from this example, it is quit obvious how recursion work, it essentially breaks down the big and complex problem by finding the similarity (the recursive parts) . and solve the problem in a much efficient way compare with what we have learned in csc108 , write a huge loop with tons of if statement.
 
   overall ,i belive recursion is a powerful tool that will come handy on my later study of computer science