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;
}
You need to sign in to view this answers
Leave feedback about this