Monday, April 9, 2018

Depth First Search and Breadth First Search implementation in Python

Graph in Python can be created with:







Sunday, April 8, 2018

Merge sort and quick sort in python

Merge Sort:

def merge_sort(sor):
    mid = len(sor)//2    
    if(len(sor)<=1):
        return sor


    left =merge_sort(sor[0:mid])
    right = merge_sort(sor[mid:])
    i=j=0 
    tar =0   
    while(i<len(left) and j<len(right)):
        if(left[i]<right[j]):
            sor[tar]=left[i]
            i = i+1        
        else:
            sor[tar] =right[j]
            j=j+1 
        tar =tar+1    
    while(i<len(left)):
        sor[tar] =left[i]
        i =i +1        
        tar=tar+1    
    while(j<len(right)):
        sor[tar]= right[j]
        j=j+1        
        tar =tar+1
    return sor


if __name__ =='__main__':
    arr = [150,4,9,26,1,5,65,2,12,1,1]
    final =merge_sort(arr)
    print (final)





Quick Sort:

def partition(arr,l,h):
    # Note for finding the pivot element and placing the pivot element in middle    
    #  start from initial index and then increase one pointer j to teh last greatest element 
   #   if small element is found swap small element with bigger that is pointed by the j pointer 
   #   
    pivot = arr[h]
    j=l
    for i in range(l,h):
        if(arr[i]<pivot):
            arr[i],arr[j]=arr[j],arr[i]
            j=j+1    arr[j],arr[h]=arr[h],arr[j]
    return  j

def quick_sort(arr,l,h):
    if(l<h):
        pivot = partition(arr,l,h)
        quick_sort(arr,l,pivot-1)
        quick_sort(arr,pivot+1,h)


if __name__ =='__main__':
    arr = [150,4,9,26,8,100,80,12]
    n= len(arr)
    quick_sort(arr,0,n-1)
    print (arr)

Binary tree creation and inorder,preorder traversal both iterative and recurrence in python

class node:
    def __init__(self,key):
        self.data=key
        self.left= None
        self.right =None
def insert(root,nd):
    if(nd.data <= root.data):
        if(root.left is None):
            root.left = nd
        else:
            insert(root.left,nd)
    else:
        if(root.right is None):
            root.right = nd
        else:
            insert(root.right,nd)
def bin_search(root,key):
    if(root is None or root.data == key):
        return root
    else:
        if(key<root.data):
            return bin_search(root.left,key)
        else:
            return bin_search(root.right,key)


def tree_inorder_traverse(node):
    if(node == None):
        return    tree_inorder_traverse(node.left)
    print(node.data)
    tree_inorder_traverse(node.right)

def inorder_iterative(node):
    stack = []
    current = node
    while(1):
        if(current is not None):
            stack.append(current)
            current = current.left
        else:
            if(len(stack)>0):
                current = stack.pop()
                print(current.data)
                current = current.right
            else:
                break
def preorder_traversal(node):
    if(node == None):
        return    print(node.data)
    preorder_traversal(node.left)

    preorder_traversal(node.right)

def preorder_iterative(root):
    stack_pre=[]
    current = root
    while(1):
        if(current is not None):
            print(current.data)
            stack_pre.append(current)
            current =current.left
        else:
            if(len(stack_pre)>0):
                current = stack_pre.pop()
                current = current.right

            else:
                break

def preorder_iterative2(root):
    stack_pre=[]
    current = root
    stack_pre.append(current)
    while(len(stack_pre)>0):
        current = stack_pre.pop()
        print (current.data)
        if(current.right is not None):
            stack_pre.append(current.right)
        if(current.left is not None):
            stack_pre.append(current.left)


if __name__ == "__main__":
    root = node(50)
    insert(root,node(20))
    insert(root,node(70))
    insert(root,node(10))
    insert(root,node(30))
    insert(root,node(60))
    preorder_traversal(root)
    value = bin_search(root,20)
    print (value.data)

    print ("iterative")
    preorder_iterative(root)