0
$\begingroup$

Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different algorithims for sorting (quick , merge and quicKInsert). My question is is there a scenario where quickInsert out performs quick sort and merge sort running time for QuickInsert would be O(nK)+O(n log n/݇K) I have to find out a combination of N(number of elements) and K value to outperform other two sorting algos What I have tried is using k = log N did not work I know insertion sort beats quick sort in small numbers but how do I find out combination based on that. Am I missing something here

$\endgroup$
3
  • $\begingroup$ It should possible to do an analysis of the number of comparisons. Would that suffice or do you need the actual running time? $\endgroup$
    – Michel
    Dec 4, 2021 at 21:08
  • $\begingroup$ @Michel: Comparisons and assignments. People often don't just sort integers. They might sort C++ objects (expensive to assign with a copy constructor, slightly better if you have a move constructor), or they might sort reference-counted pointers, also slightly expensive to move. $\endgroup$
    – gnasher729
    Apr 8 at 11:29
  • $\begingroup$ You can bind (as in upper bound) the number of assignments in terms of the number of comparisons and estimate what your actual data cost at most to move. But I assume you know that in any case. $\endgroup$
    – Michel
    Apr 9 at 15:41

2 Answers 2

0
$\begingroup$

The running time (and how it changes) of any algorithm implementation will vary across platforms (hardware, operating system, compiler etc) and the input data. So it looks hard to find a simple relation for the array size up to which insertion sort will perform better than quick sort (and that too for all inputs).

Perhaps what we can do is assume the platform factors would remain fixed and use some representative input arrays. Then test and measure time (avoiding other system noises) to find the threshold array size $K$ below which insertion sort becomes faster. Use this $K$ in the hybrid quick/insert sort to delegate to insertion sort.

$\endgroup$
0
$\begingroup$

Big-O is only relevant for large values. It won't help you at all trying to find the optimal K.

For Quicksort, you obviously would stop recursing for a subrange of 1 number which will be already sorted. You may very well handle subranges of length 2 differently as well like

if r ≤ l + 1
    if r > l and a [l] > a [r]
        exchange a[l], a[r]
    return

So now you just choose K = 3, 4, 5 etc., measure the time for the combination of quick sort with insertion sort, for a range of typical arrays, and decide depending on your measurements. It is entirely possible and actually likely that for different machines the optimal K is different. If the optimal K is not trivial in size you'd also try insertion sort with binary search to find the position where to insert.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.