#Need help with QuickSort

14 messages · Page 1 of 1 (latest)

thorny mason
#

I'm supposed to build different variations of quicksort, I have implemented some so far but I don't understand one variant. Here:
QuicksortFixedPivotInsertion fixed pivot with cut-off to insertion sort at k. Instead of stopping the recursion when the sub array only has at most one element, implement a version where sub arrays that contain at most k elements are sorted with insertion sort. k can be decided by experimentation.

What do I do?

midnight falconBOT
#

⌛ This post has been reserved for your question.

Hey @thorny mason! Please use /close or the Close Post button above when you're finished. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

grave quartz
#

ok so quicksort "normally" splits the array in two parts and calls itself recursively unless there's just a single element

#

it wants you to add another parameter (k)

#

and whenever the array has less than or equal elements than k, you stop the recursion and just sort the parts with insertionSort

thorny mason
#

or what does determines the value of k?

thorny mason
#

Anyone?

grave quartz
#

choose k to be whatever works best (gives the best performance)

#

If I had to guess, I would start with k to be 16, 32, 64 or 128

#

probably 32

#

and then check different values and how it affects performance