Answer To: This programming assignment is to implement the following three sorting algorithms and to collect...
Kamala answered on Feb 15 2023
Programming Assignment
1. A very small array , n=32, to verify correctness
Merge Sort
import random
def COMPARE(X,Y):
global COMPCOUNT
COMPCOUNT=COMPCOUNT+1
if X return True
else:
return False
def merge_sort(lst):
global count
if len(lst)>1:
mid=len(lst)//2
left=lst[:mid]
right=lst[mid:]
merge_sort(left)
merge_sort(right)
i=0
j=0
k=0
while i
if COMPARE(left[i],right[j]):
lst[k]=left[i]
i=i+1
else:
lst[k]=right[j]
j=j+1
k=k+1
while i lst[k]=left[i]
i=i+1
k=k+1
while j lst[k]=right[j]
j=j+1
k=k+1
Heap Sort
def heapify(arr, n, i):
largest = i # largest value
l = 2 * i + 1 # left
r = 2 * i + 2 # right
# if left child exists
if l < n and COMPARE(arr[i],arr[l]):
largest = l
# if right child exits
if r < n and COMPARE(arr[largest],arr[r]):
largest = r
# root
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # swap
# root.
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# maxheap
for i in range(n-1, -1, -1):
heapify(arr, n, i)
# element extraction
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
def COMPARE1(X,Y):
global COMPCOUNT
COMPCOUNT=COMPCOUNT+1
if X<=Y:
return True
else:
return False
def partition(arr,low,high):
i = ( low-1 )
pivot = arr[high]
for j in range(low , high):
if COMPARE(arr[j],pivot):
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
Quick Sort
def quickSort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
#sorted array
lst1=[]
for i in range(0,(2**5)):
lst1.append(i)
print("......................Sorted list.........................")
print(".........MERGE SORT.....")
lst=lst1.copy()
COMPCOUNT=0
print("The sorted input: ",lst)
merge_sort(lst)
print("The sorted numbers are: ",lst)
print("Number of Comparision",COMPCOUNT)
print(".........HEAP SORT.....")
arr=lst1.copy()
COMPCOUNT=0
print("The sorted input: ",arr)
heapSort(arr)
print("The sorted numbers are: ",arr)
print("Number of Comparision",COMPCOUNT)
print(".........QUICK SORT.....")
arr=lst1.copy()
COMPCOUNT=0
print("The sorted input: ",arr)
quickSort(arr,0,len(arr)-1)
print("The sorted numbers are: ",arr)
print("Number of Comparision",COMPCOUNT)
#reserve sorted array
lst1=[]
for i in range(32,0,-1):
...