Modify the quicksort function (found in the file testquicksort. py), so that it calls insertionSort (found in the file algorithms. py) to sort any sublist whose size is less than 50 items. Compare the performance of this version with that of the original one, using data sets of 50, 500, and 5000 items. Then, adjust the threshold for using the insertion sort to determine an optimal setting File: testquicksort. py
Tests the quicksort algorithm
def quicksort(lyst):
quicksortHelper(lyst, 0, len(lyst) - 1)
def quicksortHelper(lyst, left, right):
if left < right:
pivotLocation = partition(lyst, left, right)
quicksortHelper(lyst, left, pivotLocation - 1)
quicksortHelper(lyst, pivotLocation + 1, right)
def partition(lyst, left, right):
# Find the pivot and exchange it with the last item
middle = (left + right) // 2
pivot = lyst[middle]
lyst[middle] = lyst[right]
lyst[right] = pivot
# Set boundary point to first position
boundary = left
# Move items less than pivot to the left
for index in range(left, right):
if lyst[index] < pivot:
swap(lyst, index, boundary)
boundary += 1
# Exchange the pivot item and the boundary item
swap (lyst, right, boundary)
return boundary
def swap(lyst, i, j):
"""Exchanges the items at positions i and j."""
# You could say lyst[i], lyst[j] = lyst[j], lyst[i]
# but the following code shows what is really going on
temp = lyst[i]
lyst[i] = lyst[j]
lyst[j] = temp
import random
def main(size = 20, sort = quicksort):
lyst = []
for count in range(size):
lyst. append(random. randint(1, size + 1))
print(lyst)
sort(lyst)
print(lyst)
if __name__ == "__main__":
main()