SORTING ALGORITHMS Implement three sorting algorithms. Bubble sort, Insertion so
ID: 3760431 • Letter: S
Question
SORTING ALGORITHMS
Implement three sorting algorithms. Bubble sort, Insertion sort andMerge sort. Each of your
algorithms should take a text file with one element in each line as input and produce an output
of the same format. And you are not allowed to use soring libraries for implementation.
Your algorithms should bemade from the scratch.
TIME EVALUATION
Modify your code for each algorithm in such a way that the programtakes an array of integers
as input size, sorts them and output the total runtime for the algorithm.
Explanation / Answer
Bubble sort, Insertion sort and Merge sort
def bsort(l):
for i in range(len(l)-1):
for j in range(len(l)-1):
if l[j]>l[j+1]:
l[j],l[j+1]=l[j+1],l[j]
return l
def isort(l):
i=1
while i<(len(l)):
m=l[i]
j=i-1
while j>=0:
if l[j]>m:
l[j+1],l[j]=l[j],m
j=j-1
else:
break
i=i+1
return l
def merge(a,b):
l=[]
i,j=0,0
while (i<len(a) and j<len(b)):
if a[i]<b[j]:
l.append(a[i])
i=i+1
else:
l.append(b[j])
j=j+1
l=l+a[i:]
l=l+b[j:]
return l
def msort(l):
if len(l)<2:
return l
m=len(l)/2
return merge(msort(l[:m]),msort(l[m:]))
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.