- cross-posted to:
- programmerhumor@lemmy.ml
- cross-posted to:
- programmerhumor@lemmy.ml
You must log in or # to comment.
[-3, -1, main@desktop:~/Projects/TimeoutSort$ _Isn’t this basically an implementation of spaghetti sort? I’ve seriously taken the delay approach before in distributed memory situations.
Wait till you find out how the runtime manages multiple concurrent timers
it’s
while (true) { let t = Date.now(); if (timeoutMap.has(t)) timeoutMap[t](); }of course. Clearly O(n).
disclaimer
Feel free to use it. I guarantee it is bug free. Comes with express warranty. This notice is legally binding.
Then don’t complain once you get arrested…
From nowaday’s standards, that’s express warranty that lasts until you start executing your code.
why is it doing it in ordinal order?
For better usage: you don’t need to write it into console. Just write it in an array!
I know this under the name sleepSort.
Would this lead to problems if there are multiple identical and close by values? Like for example you have 100 elements each between 1 and 5
To reduce the chance of errors, you can multiply all numbers by a factor of 10, 100, 1000, 10000, … for the timeout. The higher the factor, the lower the chances of an incorrect result. And as no one asked about performance…
Maybe not peak performance but heigh CPU efficency, it’s load ist mostly 0.
As added benefit, you can then opyimise the code by dividing the number by 2, making it twice as fast. Think of the savings!
Better yet: take the square root and you get a sub-linear run time
Yes.
finally, sorting in linear time /s
It’s kind of linear, in the largest element of the array. Just not in the length of the array.
it’s in constant time then
linear in size
Can’t wait for vibe coded programs to use timeoutSort.
This is almost a bucket sort, which is practically O(n).
(I’ll leave it to the other readers to state the trade-offs)
I’m dumb, can someone ELI5 please?
The output is sorted due to the fact that for each number, a timer is started that prints out the number after waiting a number of milliseconds equal to said number.
Therefore, 1 is printed first after delaying for 1 millisecond, 5 is printed second after 5 milliseconds etc.
So all items in the array are launched simultaneuously and ran in parallel instead of sequentially?
They are launched sequentially, but run simultaneously, yes - at least some of them. And they run concurrently but not in parallel - using a single execution context, there is only a single thread, so no parallelism exist.
I see, I was only aware of sleep but that makes sense. Thanks for your insight.
Perfectly explained, thank you!
The program goes through the collection of numbers and prints each one after a delay of milliseconds equal to that number: “Print the number 20 after a 20 millisecond delay. Print the number 5 after a 5 millisecond delay. Print the number 100 after a 100 millisecond delay… etc…” effectively sorting the collection because the numbers will be printed in order from smallest to largest.
This is a clever (but impractical) way to sort a collection, because it does not require comparing any of the elements of the collection.
because it does not require comparing any of the elements of the collection
Well, if you are comparing
x + atoyandx + btoyand then both toy', theny''and so on, then are you really not comparingatob?
Race condition
Doesn’t the tortoise always win that one, too?
No
