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)

No comments:

Post a Comment