-3

Does the function qsort() in stdlib.h actually use quicksort algorithm, as the name suggests?

kBisla
  • 590
  • 2
  • 8
  • 23

2 Answers2

6

The qsort() function may be implemented using any sort algorithm that the library implementer chooses, but the name suggests that the algorithm should be close to optimal. Using an O(N2) algorithm would be permissible, but a major QoI (quality of implementation) issue.

It is worth noting that comparison is quite expensive with the qsort() interface; any sort algorithm that increases the number of comparisons to reduce the number of moves (which can also be expensive if you are not shuffling pointers) may lead to worse performance. However, that's an issue for the library implementer to be concerned with. Unless you find that the library implementation is horrid (which is pretty unlikely these days), use it and don't worry.

The C++ sort algorithm can run rings around C's qsort.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • +1 Many implementations use a duo or even trio of algorithms intermixed, depending on the data being sorted and its analysis. The Apple LLVM 4.2 chain implementation I use has an *amazing* implementation that actually unrolls a bubble-sort for tiny partitions (I *think* it was for slices smaller than 14 elements, but I would have to check to be sure) for example. – WhozCraig Aug 26 '13 at 00:14
  • Pretty sure qsort was once commonly quicksort, and that's of course average-case O(N log N) but worst-case O(N^2). Would that count as a QoI issue these days? –  Aug 26 '13 at 00:18
  • @WhozCraig Are you sure that it’s a bubble sort? That would surprise me, conventional wisdom holds that insertion sort is pretty much always more efficient … – Konrad Rudolph Aug 26 '13 at 00:18
  • 1
    @Steve314 Yes it would – deterministic quicksort is amenable to denial of service attacks by malicious (= sorted) input (smart pivot choice mitigates that somewhat but not entirely; only randomised variants can really help here). That’s a major issue for web services. More fundamentally, a *predictable* performance is required in some domains. – Konrad Rudolph Aug 26 '13 at 00:19
  • @KonradRudolph The unroll contains a stack of `if`s that are up 14 levels deep. I could certainly check, you may well be right. I find it much easier to peruse `std::sort` from the C++ side only because its in the header and I don't have to hunt down the CRT source file. =P – WhozCraig Aug 26 '13 at 00:20
  • @Steve314: the name implies it will be Quick Sort, and traditionally it was Quick Sort. However, which sub-species of Quick Sort was undefined. See [QuickSort — Choosing the pivot](http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot/) for an extensive discussion of median-of-three and related algorithms, with references to numerous external sources. You can also look up 'Fat Pivot' and 'Fit pivot', and 'Introsort'. – Jonathan Leffler Aug 26 '13 at 00:21
  • 1
    @WhozCraig That sounds more like a [sorting network](http://en.wikipedia.org/wiki/Sorting_network) than bubble sort. I’ve used that myself for a parallel task scheduler that had to sort extremely small input arrays *very* efficiently. – Konrad Rudolph Aug 26 '13 at 00:21
  • @Konrad - I didn't say "deterministic" - pretty sure the first paper describing quicksort also described randomized pivots. However, point taken - if nothing else, fast random numbers tends to mean insecure random numbers - perhaps there's some way someone could predict the seed. –  Aug 26 '13 at 00:23
  • @KonradRudolph You were *totally* right (and dare I say that hints you really need to get out more, as well as I need to *stay in* more). Its even mentioned in a comment: *"...see if insertion sort is quick"*. Just.. wow. Thanks for the info, sir. – WhozCraig Aug 26 '13 at 00:26
1

The C11 standard does not specify. So any reasonable O(n log n) would be acceptable.

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256