I'm writing a c program where I need to make arrays of different sizes (between 512 and 16384 elements) that always generate the best case for quick sort. I know that the pivot should always be in the middle, but how do I make an algorithm that creates an array of numbers where that is the case? In my partition function I pick the last element as the pivot.

I tried to make a function based on a reply I found in another thread, but the run times I get from sorting those arrays are bigger than what I get from average case.

CodePudding user response：

Assuming the goal is to find a permutation of {0, 1, 2, ..., n-1} which results in an optimal quicksort...

Write a modified quicksort that works on an array of struct {int orig_index; int value}, originally intialized to {{0, -1}, {1, -1}, {2, -1}, ..., {n-1, -1}} .When you pick a pivot using the same method as your actual quicksort function (eg: the last value in the current range), assign its value to the middle value of the current range (ie: an optimal pivot value), and then partition the array as usual (using the same partition method as your actual quicksort function), assuming the first half of the values are less than the pivot, and the second half of the values are greater than the pivot (although you are free to choose which half are greater and which half larger, as long as there's the right number of elements of each). At the end, you will have values from 0 to n-1 coupled with where they would have been found in the original array.

CodePudding user response：

Using Hoare partition scheme with the middle element as the pivot, two best cases are data already sorted, or all elements equal.

For Lomuto using middle element as pivot (then swapping to either end), best case is already sorted data. All elements equal is worst case for Lomuto partition scheme.