9 Recurrence relations and recursive algorithms

Example 15:Page 421

print "MERGE SORT"
alist=[65,43,22,54,87,11,76,48,30,60,19,75,94,27,58,80]#List to be sorted
def mergesort(alist):
    print "Splitting",alist
    if len(alist)>1:
        
        mid=len(alist)/2
        left_half=alist[:mid]
        right_half=alist[mid:]#Spltting into halves
        mergesort(left_half)
        mergesort(right_half)#Recirsive split to obtain values
        i=0
        j=0
        k=0#Varaibles for indexing
        while i<len(left_half) and j<len(right_half):
            if left_half[i]<right_half[j]:
                alist[k]=left_half[i]#Puts the minimum value in the beginning
                i=i+1
            else:
                alist[k]=right_half[j]
                j=j+1
            k=k+1
        while i<len(left_half):
            alist[k]=left_half[i]#Combine left sorted elements to the whole list
            i=i+1
            k=k+1
        while j<len(right_half):
            alist[k]=right_half[j]#Combine right sorted elements to the wholw list
            j=j+1
            k=k+1
    print "Merging",alist
   
mergesort(alist)
print(alist)

MERGE SORT
Splitting [65, 43, 22, 54, 87, 11, 76, 48, 30, 60, 19, 75, 94, 27, 58, 80]
Splitting [65, 43, 22, 54, 87, 11, 76, 48]
Splitting [65, 43, 22, 54]
Splitting [65, 43]
Splitting [65]
Merging [65]
Splitting [43]
Merging [43]
Merging [43, 65]
Splitting [22, 54]
Splitting [22]
Merging [22]
Splitting [54]
Merging [54]
Merging [22, 54]
Merging [22, 43, 54, 65]
Splitting [87, 11, 76, 48]
Splitting [87, 11]
Splitting [87]
Merging [87]
Splitting [11]
Merging [11]
Merging [11, 87]
Splitting [76, 48]
Splitting [76]
Merging [76]
Splitting [48]
Merging [48]
Merging [48, 76]
Merging [11, 48, 76, 87]
Merging [11, 22, 43, 48, 54, 65, 76, 87]
Splitting [30, 60, 19, 75, 94, 27, 58, 80]
Splitting [30, 60, 19, 75]
Splitting [30, 60]
Splitting [30]
Merging [30]
Splitting [60]
Merging [60]
Merging [30, 60]
Splitting [19, 75]
Splitting [19]
Merging [19]
Splitting [75]
Merging [75]
Merging [19, 75]
Merging [19, 30, 60, 75]
Splitting [94, 27, 58, 80]
Splitting [94, 27]
Splitting [94]
Merging [94]
Splitting [27]
Merging [27]
Merging [27, 94]
Splitting [58, 80]
Splitting [58]
Merging [58]
Splitting [80]
Merging [80]
Merging [58, 80]
Merging [27, 58, 80, 94]
Merging [19, 27, 30, 58, 60, 75, 80, 94]
Merging [11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]
[11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]

Example 17:Page 424

print "BINARY SEARCH"
array=["" for i in range(100)]
temp=0#Variable checks if the element has been found. Initialised to zero, if it retains the same value till the end, then the element is not in the given list
n=input("Enter the number of elements")
print "Enter the elememts in sorted order"
for i in range(0,n):
    array[i]=input()#Input the numbers in ascending order
item=input("Enter the item to be searched")
first=0#
last=n-1
while first<=last:
    mid=(first+last)/2#Finds the middle element
    if item==array[mid]:
        print "Search is successfully completed"
        temp=mid
        print "The item is in position",temp+1
        
    if item<array[mid]:#Divides the array into half depending on the value to be searched
        last=mid-1
    else:
        first=mid+1
if temp==0:
        print "Search is not successfully completed"
    

BINARY SEARCH
Enter the number of elements7
Enter the elememts in sorted order
9
16
25
49
50
67
84
Enter the item to be searched67
Search is successfully completed
The item is in position 6