Sorting Algorithms

Sadly, I was unable to post last week due to an incredible amount of studying i had to attend to.  Nonetheless, heres a quick refresher of the material we covered last week.  We wrapped up our study of proofs and basic mathematical structure for proof arguments.  We went over proof problems involving added complexity, such as epsilon delta proofs.  In addition, we covered ways not to do proofs such as proof by intimation or proof by puns.

Just as a side note: in the lecture slides it was shown that the statement "trivial" is an example of proof by intimidation, and should generally be avoided.  However, it seems authors of physics and mathematics textbooks use the term "trivial" on a regular basis.

The next topic of discussion and most of the focus of the past week was sorting algorithms. We began discussing the basic sorting algorithms including merge sort and bubble sort.  Heres a quick overview of the two sorting techniques.

Bubble sort: Its a sorting algorithm that compares the adjacent items in a list, and interchanges them if the are in the wrong order. The python implementation of bubble sort is shown below.

 def bubble_sort(l): 
 """ Algorithm for bubble sort""" 
 for i in range(len(l)):
     for j in range(len(l)-1-i): 
         if l[j] > l[j+1]:  
             l[j], l[j+1] = l[j+1], l[j]

Merge sort: Its a recursive sorting algorithm that use a "divide and conquer approach".  Namely, it divides the unsorted list into smaller sublists, and sorts each of the smaller sublists, and combines everything together to obtain the sorted list.  The implementation is not included here but can be found at http://www.geekviewpoint.com/python/sorting/mergesort.