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
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:
(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:
(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:
(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:
0 Comments