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.