Sorting and its Efficiency

Selection Sort:
The algorithm is going to run unless the given list is empty.
It would find the smallest element in the list and will append in the new list and so the loop is going to iterate over every element of the list to find the smallest element. Therfore, every cycle it is going to have 'n' iterations , where n is the length of the list.

def selectionSort(alist):
   for fillslot in range(len(alist)-1,0,-1):
       positionOfMax=0
       for location in range(1,fillslot+1):
           if alist[location]>alist[positionOfMax]:
               positionOfMax = location

       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

Insertion Sort:
The algorithm is going to have a look at one element after the other and will insert the element in the list at the correct position. This will also be iterated on all the elements of the list and so will have 'n' iterations where n is the length of the list.

def insertionSort(alist):
   for index in range(1,len(alist)):

     currentvalue = alist[index]
     position = index

     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1

     alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

Bubble Sort:
Bubble sort goes through the list again and agai and exchanges the neighbouring elements (if necessary) and stops if no changes have been made while going through the list once. Hence, it will be iterated 'n*n' times where n is the length of the list.

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

Merge Sort:
It divides the list into two subsequent parts and sort them recursively and finally after sorting it merges back all the sorted lists to a original length sorted list. Since, it divides the list and performs the recursion, so it takes 'n.lgn' iterations where n is the length of the list.

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Quick Sort:
It sorts the list using a pivot. It picks up a pivot (an element) from the list and then performs comparison bwtween the pivot and every element of the list recursively into two different parts - one which is greater than pivot and the other which is less than pivot. After sorting it recursively it merges the first part (lower than the pivot), pivot and the second part (greater than pivot). Since, it is also subdividing the list hence it takes 'nlgn' iterations.

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and \
               alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and \
               rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

For all of the above sorting, when the length of the list becomes really long the best sorting algorithm comes out to be Merge sort with the worst case of 'n.lgn' whereas the worst case for quick sort becomes 'n^2' although it also divides the list, but when the length becomes too long the subdivision into two parts and their sorting takes too long run time. The worst algorithm with the too long list becomes Bubble Sort, which has to work on every element of  list many times. 

Recursion

Recursion is mainly used in nested lists. A nested lists is - lists within the list. We know that a list can be grouped inside another lists in a variety of ways.
To sum all the numbers in a nested list, we need to traverse the list, visiting each of the elements within the nested list, adding all those and repeating the same process for all the elements in the list which are list and then, summing up all the results within the base/main list to find the sum.
In order to decrease our efforts and coding for the long and lists with huge nested depths, Modern programming languages uses or supports Recursion - which means that function can call themselves within their definitions.

For example:

def recursive_sum(nested_num_list):
    sum = 0
    for element in nested_num_list:
        if type(element) == type([]):
            sum = sum + recursive_sum(element)
        else:
            sum = sum + element
    return sum

 The body of recursive_sum consists mainly of a for loop that traverses nested_sum_list. Here element is a numerical value, which is simply added to the sum but if an element comes out to be a list then it will  again run the same function for that elemental list. Therefore, the simple addition of the numerical values in the lists turn out to be the base case ( general implementation of the function) and the recursive call of the function turns to implement the same base case for all the elements within the sub-lists of the list.

This is the general way to deal with all the nested lists in programming in Python. i.e. first think of its base case( what the functions wants to deal with in general) and then make a recursive call to a function for all the other cases.

It surely turns out to be complicated in many cases, but with the more and more practice and by recognizing the base cases, recursion becomes the easiest way to deal with the Nested Lists with more and complicated Nested Depths.

Object Oriented Programming - Week : 3

This week was quite interesting for me as I learned some more new features about Stack ADT like how to make a subclass in an already existing class, to raise exceptions in the result. Although the week was quite interesting, but still I faced some problems in making a subclass as well as using sets and lists in Stack. But, after a discussion with my TA during the lab, everything was clear. Finally. I can use the functions of Stack taught till now easily. After these three weeks of programming, I'm really excited to gather more information for programming in the coming weeks.