Implement Sorting Algorithms a.Bubble sort b. Insertion sort c. Quick sort d. Merge Sort

algorithm:- it is a process or set of rules which is used to solve the operation by a sequence. 

in the other words an algorithm is a set of rules and instruction that define step by step how to problem solve 

algorithm

a. Bubble sort :- in the bubble sort algorithm adjacent element swapping repeatedly until they are arrange in right order.  



b. Insertion sort

c. Quick sort           

d. Merge Sort

(a).Bubble sort

def bubbleSort(alist):

    for i in range(len(alist)-1,0,-1):

        for j in range(i):

            if alist[j]>alist[j+1]:

                temp=alist[j]

                alist[j]=alist[j+1]

                alist[j+1]=temp

alist=[]

n=int(input("Enter number of element:"))

while(n>0):

    x=int(input("Enter element:"))

    alist.append(x)

    n=n-1

bubbleSort(alist)

print(alist)

output:

Bubble sort


(b).Insertion sort

def insertionSort(alist):

    for i in range(1,len(alist)):

        current=alist[i]

        hole=i

        while hole>0 and alist[hole-1]>current:

            alist[hole]=alist[hole-1]

            hole=hole-1

        alist[hole]=current

alist=[]

n=int(input("Enter number of element:"))

while(n>0):

    x=int(input("Enter element:"))

    alist.append(x)

    n=n-1

insertionSort(alist)

print(alist)

output:

Insertion sort

(c).Quick Sort

def quickSort(alist,start,end):

    if start<end:

        loc=partition(alist,start,end)

        quickSort(alist,start,loc)

        quickSort(alist,loc+1,end)

def partition(alist,start,end):

    pivot=alist[start]

    left=start+1

    loc=end

 

    flag=0

    while flag!=1:

        while left<=loc and alist[left]<=pivot:

            left=left+1

        while alist[loc]>=pivot and loc>=left:

            loc=loc-1

        if loc<left:

            flag=1

        else:

            temp=alist[left]

            alist[left]=alist[loc]

            alist[loc]=temp

        temp=alist[start]

        alist[start]=alist[loc]

        alist[loc]=temp

 

        return loc

 

alist=[]

n=int(input("Enter number of elements"))

while(n>0):

    x=int(input("Enter element"))

    alist.append(x)

    n=n-1

print("Original list",alist)

quickSort(alist,0,len(alist)-1)

print("Sorted list",alist)

output:

Quick Sort

(d) merge Sort

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) 

output:

merge Sort


Post a Comment

0 Comments