Sorting and Efficiency

  The topic of this week is sorting and efficiency. So, the first question arise in my head is: what exactly is sorting and efficiency, and how is it relate to programming? According to wikipedia: A sorting algorithm is an algorithm that puts elements of a list in a certain order. Here is an example I found on the internet which explains how sorting algorithm works (source:http://hetland.org/coding/python/quicksort.html):
 #!/usr/bin/env python

# Written by Magnus Lie Hetland 

"Everybody's favourite sorting algorithm... :)"

def partition(list, start, end):
    pivot = list[end]                          # Partition around the last value
    bottom = start-1                           # Start outside the area to be partitioned
    top = end                                  # Ditto

    done = 0
    while not done:                            # Until all elements are partitioned...

        while not done:                        # Until we find an out of place element...
            bottom = bottom+1                  # ... move the bottom up.

            if bottom == top:                  # If we hit the top...
                done = 1                       # ... we are done.
                break

            if list[bottom] > pivot:           # Is the bottom out of place?
                list[top] = list[bottom]       # Then put it at the top...
                break                          # ... and start searching from the top.

        while not done:                        # Until we find an out of place element...
            top = top-1                        # ... move the top down.
            
            if top == bottom:                  # If we hit the bottom...
                done = 1                       # ... we are done.
                break

            if list[top] < pivot:              # Is the top out of place?
                list[bottom] = list[top]       # Then put it at the bottom...
                break                          # ...and start searching from the bottom.

    list[top] = pivot                          # Put the pivot in its place.
    return top                                 # Return the split point


def quicksort(list, start, end):
    if start < end:                            # If there are two or more elements...
        split = partition(list, start, end)    # ... partition the sublist...
        quicksort(list, start, split-1)        # ... and sort both halves.
        quicksort(list, split+1, end)
    else:
        return

    
if __name__=="__main__":                       # If this script is run as a program:
    import sys
    list = map(int,sys.argv[1:])               # Get all the arguments
    start = 0
    end = len(list)-1
    quicksort(list,start,end)                  # Sort the entire list of arguments
    import string
    print string.join(map(str,list))           # Print out the sorted list

Now, algorithmic efficiency on the other hand are the properties of an algorithm which relate to the amount of resources used by the algorithm. Efficiency on one hand can be thought as  the productivity for a repeating or continuous process. Here is an example of how to determine the efficiency of an algorithm(source:http://www.cprogramming.com/tutorial/computersciencetheory/algorithmicefficiency2.html):for(int x=0; x<n; x++)

 {
   int min = x;
   for(int y=x; y<n; y++)
   {
  if(array[y]<array[min])
    min=y;
   }
   int temp = array[x];
   array[x] = array[min];
   array[min] = temp; 

 }
We compute that the order of the outer loop (for(int x = 0; ..)) is O(n); then, we compute that the order of the inner loop is roughly O(n). Note that even though its efficiency varies based on the value of x, the average efficiency is n/2, and we ignore the constant, so it's O(n). After multiplying together the order of the outer and the inner loop, we have O(n^2).
It may look as simple as the example shows, but the actual operation is much harder, and sometimes i still have difficulties solving this problems. Sorting and efficiency can be quit challenging, I will continue to work on it until i am confident with this sort of topic. 

Recursion

  When talking about recursion in programming (Python, Java...etc.), the first problem raising up in my head is " what is recursion" ? From my understanding, recursion is a method that is defined within its own definition. In other word, recursion uses itself to operate as a function. So, the next question is why is recursion so powerful? Or why is recursion necessary in programming? According to Wikipedia - The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.If it was still hard to understand, I will show a very simple example of recursion. void myMethod( int counter)
{
if(counter == 0)
     return;
else
       {
       System.out.println(""+counter);
       myMethod(--counter);
       return;
       }
}

(source - http://danzig.jct.ac.il/java_class/recursion.html)

As we can see, this recursion is not infinite, it is essentially a loop. When should we use recursion to solve problems? We use recursion when we can see that our problem can be reduced to a simpler function to be solved.
  Now lets talk about the characteristics of recursion:
  1. Every recursion function should have a simple base case that is the final reduced solution, and of course a       return value.
  2. A very sophisticated problem set that is intended for recursion to happen.
  3. A recursive call which passes the simpler problem back into the method.
Now we have discuss about recursive functions, I came to a better understanding of recursion. Throughout these weeks, I learned how to solve recursive programming, how it works, and how to make such functions.
I will continue to practice recursion, because I know it is very important in not only python, but it is also very important in other  programming languages.

Object Oriented Programming

    By definition Object- Oriented programming is a type of programming that uses characteristics similar to reality to define classes and objects. When I first saw this term, I didn’t know what it really is. I thought it would be something very confuse and sophisticated. After some research online (looking at Wikipedia, etc.), I had a better understanding of what exactly is Object-oriented programming. Eventually, it is a different style of programming that follows a unique sets of principles. For example: An object- oriented program usually contains different types of objects (adopted from Wikipedia). Each objects is then corresponding to another real world object or concept. A human is an object, Xiangyu Zhang is also an object, and I can correspond to the object human. I can call different methods such as: sleep, eat, talk, and watch. These methods can also be called by another object Henry. Overall, the goal of object- oriented programming is to provide a better understanding of the code and being more practical to real life situations. It also can be maintained easily since the methods and objects and classes are all separated.