HybridQuickSort

Submit solution
Points: 10
Time limit: 4.0s
Memory limit: 64M
Author:
s_mansi
Problem type
Allowed languages
C, C++, Python

Implement a hybrid algorithm with the combination of quick sort and insertion sort. As the name suggests, the Hybrid algorithm combines more than one algorithm.

Why Hybrid algorithm:

Quicksort algorithm is efficient if the size of the input is very large. But, insertion sort is more efficient than quick sort in case of small arrays as the number of comparisons and swaps are less compared to quicksort. So we combine the two algorithms to sort efficiently using both approaches.

Hint

The idea is to use recursion and continuously find the size of the array. If the size is greater than the threshold value (say 10), then the quicksort function is called for that portion of the array. Else, insertion sort is called.

Input1

24 97 40 67 88 85 15 66 53 44 26 48 16 52 45 23 90 18 49 80 23

Output1

15 16 18 23 23 24 26 40 44 45 48 49 52 53 66 67 80 85 88 90 97

Can you plot for a very large sequence of random numbers N=10000, 1000000?. Observe the behavior and plot N vs time.

Comments for space and time complexity of this hybrid algorithm.

Comments


  • 0
    sri_venkatesh1  commented on March 19, 2023, 10:52 a.m.

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

    def partition(arr, low, high): pivot = arr[high] i = j = low for i in range(low, high): if arr[i]<pivot: a[i], a[j]= a[j], a[i] j+= 1 a[j], a[high]= a[high], a[j] return j

    def quick_sort(arr, low, high): if low<high: pivot = partition(arr, low, high) quick_sort(arr, low, pivot-1) quick_sort(arr, pivot + 1, high) return arr

    def hybrid_quick_sort(arr, low, high): while low<high:

        # If the size of the array is less
    # than threshold apply insertion sort
    # and stop recursion
    if high-low + 1<10:
        insertion_sort(arr, low, high)
        break

    else:
        pivot = partition(arr, low, high)


        if pivot-low<high-pivot:
            hybrid_quick_sort(arr, low, pivot-1)
            low = pivot + 1
        else:

            hybrid_quick_sort(arr, pivot + 1, high)
            high = pivot-1

    a = [ 24, 97, 40, 67, 88, 85, 15, 66, 53, 44, 26, 48, 16, 52, 45, 23, 90, 18, 49, 80, 23 ] hybrid_quick_sort(a, 0, 20) print(a)