Hybrid algorithm that combines Insertion Sort and Quick Sort

user_16244265 0
Viewed 196

I'm trying to implement a hybrid algorithm that combines Insertion Sort and Quick Sort to get the desired features of both in such a way so that when the elements are fewer than 50 in a quicksort step, Insertion Sort is used and for greater than 50 the elements are merged using the Quick Sort algorithm. I attempt to sort the elements to the left of the pivot_index and those to the right of the pivot_index using insertion sort if they are less than 50 by passing a slice instance of the original list as a parameter into my insertionSort function but my list remains the same, partitioned yet unsorted. Any indictors to fix this issue would be deeply appreciated.

from random import randint

def insertionSort(arr):
    
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j = j - 1
            
        arr[j+1] = key
        
def partition(a, low, high): #lomuto partition scheme
    i = low - 1 #directly to the left of our specified low-high range
    pivot = a[high] #pivot is the last value in our range, the index equal to high parameter
    for j in range(low, high):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[high] = a[high], a[i+1]
    return i+1

def quicksort_inplace(a, low=0, high=None):
    if high == None:
        high = len(a) - 1
        
    if low < high:
        pivot_index = partition(a, low, high) #partition around pivot
        print("The pivot_index is:", pivot_index)
        print("Low is:", low)
        print("High is:", high)
        
        if pivot_index - low <= 50:
            insertionSort(a[low:pivot_index])
            
        elif high - pivot_index <= 50:
            insertionSort(a[pivot_index+1:high])
            
        else:
            quicksort_inplace(a, low, pivot_index - 1) #sort lower half
            quicksort_inplace(a, pivot_index + 1, high) #sort upper half
        
def create_arr(size=10):
    return [randint(0,50) for _ in range(size)]

arr = create_arr()
print(arr)
quicksort_inplace(arr)
print()
print("The sorted array is:", arr)
data-structures python-3.x sorting python
1 Answers

Slicing a list results in shallow copies of the original sublist, so the original will not be modified by passing a slice instance to insertionSort. That is why the list is not sorted after partitioning in your code.

To apply insertion sort in-place, you can pass low and high as arguments:

def insertion_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        j = i
        while j > low and arr[j] < arr[j - 1]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1

It would also be more efficient to check if the size is below the threshold before partitioning. The quicksort_inplace function can then be rewritten as follows (with THRESHOLD = 50 in this case):

def quicksort_inplace(a, low=0, high=None):
    if high is None:
        high = len(a) - 1

    if low < high:
        if high - low + 1 < THRESHOLD:
            # Size of the subarray is less than the threshold, insertion sort
            insertion_sort(a, low, high)
            return
        # Size of the subarray is greater than the threshold, quicksort
        pivot_index = partition(a, low, high)
        print("The pivot_index is:", pivot_index)
        print("Low is:", low)
        print("High is:", high)
        quicksort_inplace(a, low, pivot_index - 1)
        quicksort_inplace(a, pivot_index + 1, high)

If the threshold is 50, the test array should obviously be much larger than 10 to properly test the function, otherwise you are only testing insertion sort.

user_95041550
Related