2

I heard a long time ago that the implementation of the qsort function is the quick sorting algorithm and has a worst-case time complexity of n^2.

But recently when I was trying to construct a set of data that would allow the qsort function to time out, I discovered that its implementation is not exactly the same as the widely known quick sort algorithm, and that it uses many optimisation tricks.

For example, there is a comment in the glibc implementation

/* Select median value from among LO, MID, and HI. Rearrange
LO and HI so the three values are sorted. This lowers the
probability of picking a pathological pivot value and
skips a comparison for both the LEFT_PTR and RIGHT_PTR in
the while loops. */

So how to construct an array to make qsort() having n^2 time complexity? Although I have read the source code of qsort in glibc, I still can't come up with a constructor method.

I've tried ascending, descending and half up half down arrays, but none of these constructors work.

for (int i = 0; i < N / 2; i++)
{
    a[i] = i;
}
for (int i = N / 2; i < N; i++)
{
    a[i] = N - 1 - i;
}

and this

for (int i = 0; i < N; i++)
{
    if (i & 1)
        a[N - 1 - i / 2] = i;
    else
        a[i / 2] = i;
}
12
  • Per the Wikipedia page, the worst case for partitioning occurs when one of the sublists is size n−1 for the first partition, n−2 for the second, and so on. So, take the C code for the implementation you are working with and figure out, by hand, how it chooses the first pivot. Then change every other element to be on one side of that pivot. Then figure out how it chooses the second pivot. Again change every other element in the first sublist to be on one side of the pivot. Repeat… Commented Oct 18, 2024 at 15:11
  • 3
    qsort() is not synonymous to "Quick Sort". The algorithm implement in a specific library is the choice of the implementors, not a requirement from the Standard. Commented Oct 18, 2024 at 15:12
  • 5
    This article, "A Killer Adversary for Quicksort" describes the process quite well. cs.dartmouth.edu/~doug/mdmspe.pdf Commented Oct 18, 2024 at 15:17
  • 1
    @JimMischel - so stack space complexity is limited to O(log(n)), but worst case time complexity remains at O(n^2). Processing smaller partition first dates back to Hoare's original quicksort where there was no native stack, so it was iterative and used a software stack that he called a "nest" at the time. Larger partition indexes were pushed on to the "nest", and the code looped back to process the smaller partition. I don't know about Visual Studio's qsort(), but it's C++ std::sort() does switches to heap sort at some recursion level, limiting worst case time complexity to O(n log(n)). Commented Oct 19, 2024 at 0:27
  • 1
    @pmg You are right, after reading the glibc-2.40 source code, I find that the latest qsort() implementation actually uses heap sort and merge sort. Commented Oct 19, 2024 at 13:14

0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.