5 ms·
How Inefficient Can a Sort Algorithm Be? (2012) [pdf]
- yogsototh 8y agorelevant: https://byorgey.wordpress.com/2019/02/16/worstsort/ https://byorgey.wordpress.com/2019/02/16/worstsort/
- xorfish 8y agoHow inefficient can a sort algorithm be with O(1) or O(n) memory usage?
- karmakaze 8y agoRandom shuffle, verify if sorted.
- cookingrobot 8y agoMake a random list, see if it’s sorted, then see if it’s the same as your original set.
- smartstakestime 8y agoO(2 * n)
- anonytrary 8y agoO(2*n) == O(n)
- augustk 8y agoOr with common mathematical notation: O(2*n) = O(n)
- deugtniet 8y agoFrom the pdf "3 Worstsort: the final solution" Reminds me of a German statistics professor that taught me the basics of contemporary statistics. This guy would often say "final solution" with a thick German accent, which was kinda funny to hear. But after a couple of lectures I did discreetly tell him about the cultural annotations behind this term. Afterwards he was a bit more modest in its usage.
- deleted 8y ago[deleted]
- majewsky 8y agoHow can someone say "final solution" with a thick German accent? I'm German myself and when I try to pronounce it with deliberately thick accent, it doesn't change all that much.
- rocqua 8y agoI'd guess something like 'ze final zolution'. With the second z a lot less pronounced than the first. Mostly the pronunciation of 'the' by Germans is easy to notice.
- majewsky 8y agoThe most obvious giveaways are pronouncing "the" like "s" and "w" like "v". Also, consonants in general are pronounced too hard, making the pronunciation less "flowing".
- gambiting 8y agoSleep sort is still my favourite - if you're sorting numbers, just spawn a new thread for each number, make it sleep that number of milliseconds and print out the number after waking up. After the largest number of milliseconds elapse, you have the sorted list of numbers nicely printed out.
- saagarjha 8y agoOf course, then you're just relying on your scheduler, which may or may not actually do the sort correctly.
- tinus_hn 8y agoThe scheduler doesn’t have a hard job if all but 1 thread is sleeping.
- benchaney 8y agoFiguring out which threads to wake up when is an equivalent problem to sorting. The kernel has to maintain a queue of threads sorted on their sleep times in order to implement the sleep syscall in the first place
- emilfihlman 8y agoIsn't sleep sort equivalent to gravity sort?
- Taniwha 8y agomake a linear pass through the data, if they are in order quit, otherwise swap two random entries and repeat
- martin_a 8y agoSo, the minimum running time for this would be O(1), but can one estimate the maximum? I don't see how, but maybe I'm missing something.
- astrobe_ 8y agoThis is known as BoZosort [1], which is said to be O(n!) on average. [1] https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort
- kevinwang 8y agoI think it may be another factor of n slower than that Edit: wow nevermind, I just read the paper linked to bozo sort in wikipedia. They conjecture that it's O(n!) whereas bogosort is Omega(n*n!). Wow, that's surprising!
- Rainymood 8y agoWhy is bubblesort consistently spelled as bublesort?
- faceplanted 8y agoBecause the people spelling it wrong Just Haven't Met You yet
- joosters 8y agoThis still feels like ... cheating to me, if that's not too strong a word. If your algorithm for sorting a list involves generating a bigger list and then sorting that, then it's obvious that by recursion, you can make your sort function take forever.
- crave_ 8y agoA program that does not halt is not an algorithm. If you want to create a sorting algorithm, it has to halt, i.e. not run forever.
- candiodari 8y agoNot seeing that in either the definition and essentially all control algorithms, like say PID control, are meant to run "forever" (meaning longer than you can foresee in the code, they need an infinite loop)
- frabert 8y agoYou could consider that in PID control the actual algorithm is the single iteration, after which the output is sent out and a new set of inputs comes in, thus restarting the algorithm. In an endless iteration, you never give out any outputs
- candiodari 8y agoYou can't run PID in a single iteration. The integration and differentiation parts would be 0 in any single iteration, and so it's quite PID control if you look at it that way. The description of the algorithm doesn't make much sense in a single iteration either.