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