So, I was tasked to create a hybrid sort function in python that would utilize bubble and merge sorts. The idea is simple; as long as the value T (threshold) is exceeded, merge sort should run recursively, whereas when the value is less than or equal to T, bubble sort is called. This slightly optimises the original merge sort function.
This is the code I've written:
def bubbleSort(arr, l, h):
isSwapped = False
size = h - l
for i in range(size-1):
for j in range(0, size-i-1):
if arr[j] > arr[j + 1]:
isSwapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not isSwapped:
return
def merge(arr, l, m, r):
size1 = m - l + 1
size2 = r - m
l_arr = [0] * size1
r_arr = [0] * size2
for i in range(0, size1):
l_arr[i] = arr[l + i]
for j in range(0, size2):
r_arr[j] = arr[m + 1 + j]
# merge
i = 0
j = 0
k = l
while i < size1 and j < size2:
if l_arr[i] <= r_arr[j]:
arr[k] = l_arr[i]
i += 1
else:
arr[k] = r_arr[j]
j += 1
k += 1
while i < size1:
arr[k] = l_arr[i]
i += 1
k += 1
while j < size2:
arr[k] = r_arr[j]
j += 1
k += 1
def mergeSort(arr, l, r):
if l < r:
m = l + (r - l) // 2
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
merge(arr, l, m, r)
else:
return
def hybridMergeSort(arr, l, r):
T = 16
while l < r:
if len(arr) <= T:
bubbleSort(arr, l, r)
break
else:
m = len(arr) // 2
hybridMergeSort(arr, l, m)
hybridMergeSort(arr, m + 1, r)
merge(arr, l, m, r)
Similar logic worked for a hybrid quick-sort algorithm. I can't figure out what the issue is. It always returns an error: RecursionError: maximum recursion depth exceeded. The same error is not returned when the mergeSort() function itself is used. I'm trying to use them for a random array of length 1000 by-the-way. I feel like the number of recursions should be the same?
Am I missing something?
There are multiple problems in your code:
In bubbleSort:
you use the wrong index in the inner loop: you should shift the index range by l.
you should reset isSwapped to False before the inner loop to stop the outer loop as soon as possible.
since l and h are both included, the number of elements in the slice is h - l + 1, so the ranges are off by one.
def bubbleSort(arr, l, h):
for i in range(h - l):
isSwapped = False
for j in range(l, h-i-1):
if arr[j] > arr[j + 1]:
isSwapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not isSwapped:
return
in hybridMerge:
while l < r: is incorrect: it is causing an infinite loop as neither l nor r are modified inside the loop body. Just write
if l < r:
testing if len(arr) <= T is incorrect: you should test if the length of the slice is smaller or equal to T,ie: if h - l is less than T:
if r - l < T
similarly, the mid point m must be computed from h and l, not from the length of the array. This is the cause of the infinite recursion.
m = l + (r - l) // 2
Here is a modified version:
def bubbleSort(arr, l, h):
for i in range(h - l):
isSwapped = False
for j in range(l, h-i-1):
if arr[j] > arr[j + 1]:
isSwapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not isSwapped:
return
def merge(arr, l, m, r):
size1 = m - l + 1
size2 = r - m
l_arr = arr[l : m+1]
r_arr = arr[m+1 : r]
# merge
i = 0
j = 0
k = l
while i < size1 and j < size2:
if l_arr[i] <= r_arr[j]:
arr[k] = l_arr[i]
i += 1
else:
arr[k] = r_arr[j]
j += 1
k += 1
while i < size1:
arr[k] = l_arr[i]
i += 1
k += 1
while j < size2:
arr[k] = r_arr[j]
j += 1
k += 1
def mergeSort(arr, l, r):
if l < r:
m = l + (r - l) // 2
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
merge(arr, l, m, r)
else:
return
def hybridMergeSort(arr, l, r):
T = 16
if r - l < T:
if l < r:
bubbleSort(arr, l, r)
else:
m = l + (r - l) // 2
hybridMergeSort(arr, l, m)
hybridMergeSort(arr, m + 1, r)
merge(arr, l, m, r)