1) yes. 2) I think you're under a misconception that the C qsort function has anything to do with quicksort aside from a historical choice of naming...
-
-
Replying to @RichFelker @vyodaiken
qsort is a function to perform comparison sorts that necessarily succeeds (has no interface for failure) and as such needs to be O(1) or effectively O(1) space. It should (QoI) also be efficient independent of input.
1 reply 0 retweets 1 like -
Replying to @RichFelker @vyodaiken
Quicksort can meet effective O(1) space (log n is effectively a constant 32 or 64) but can't be made O(n log n) time without really bad constant, and O(n²) is not nice.
1 reply 0 retweets 1 like
Replying to @RichFelker @vyodaiken
Real-world quicksorts aiming to be safe against all inputs are introsorts (intro=introspective) -- they measure for bad-case pivoting & switch to heapsort if they detect it.
2:10 PM - 29 Jun 2018
0 replies
0 retweets
1 like
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.