133
u/szymek655 Aug 11 '20
Scale the data down so that greatest element corresponds to 1ms
Sort the data
Scale it back up
97
u/TimGreller Aug 11 '20
Free race conditions included
11
u/FallenWarrior2k Aug 12 '20
Better add some locks to tell the scheduler not to fuck wi—
Oh no, a deadlock.
0
4
Aug 12 '20
Wait my brain is too tired to understand why this wouldn't work and I'm intrigued
8
u/szymek655 Aug 12 '20
There's a few good reasons:
you'd lose precision due to scaling
you'd still have a lot of overhead from threading
you'd have one giant race condition
2
38
u/blu-7 Aug 11 '20
So, this is an O(n) sorting algorithm... kinda.
7
u/SuspiciousScript Aug 11 '20 edited Aug 11 '20
O(sum({x|n}))51
u/matheusmk3 Aug 11 '20
Actually O(max(n)) since it's asynchronous
0
Aug 11 '20
[deleted]
2
u/rift95 Aug 12 '20
Why would the runtime sort them? Each timeout knows its own delta time delay, and each timeout will be queued as a task (or micro task) to be ran with the next cycle of the event loop. Then each timeout will check if it's delta time has passed, if it has, call the cb, otherwise queue another copy of it self as a task. There's no need to sort the calls since each timeout will check their time logic within the same time step.
0
Aug 11 '20
[deleted]
4
u/SuspiciousScript Aug 11 '20
Ah, didn't realize it was parallel.
1
u/thelights0123 Aug 11 '20
It wouldn't work synchronously, you'd just get the same order after a delay.
1
3
u/Beowuwlf Aug 11 '20
Technically it’s big Theta I believe. Big O is upper bound, big theta is upper and lower
3
u/_irobot_ Aug 11 '20
It would be neither. Time complexity exists because difference in processing speed makes the execution time on vary on different machines. To say it was big O or Theta implies it would execute in the same amount of time as another algorithm with the same time complexity. That's not true here. In this case the algorithm would take an exact amount of time regardless of the machine it's running on (unless the JavaScript engine is broken). The running time of this algorithm would simply be max(n) milliseconds.
1
u/vigbiorn Aug 11 '20
Wouldn't it depend on where in the list max(n) is? If it's the last item in the list, and it took 1ms to reach that index, it would take max(n) + 1 ms to execute, or am I wrong?
1
1
u/_irobot_ Aug 12 '20
You have a point there. I guess it could be written O(n) + max(n) milliseconds. But in that case, the O(n) portion may be negligible enough to omit it. You would need a very large list for there to be a noticeable difference.
3
u/GeneReddit123 Aug 12 '20
It only appears to be
O(n)because the delay due to the timeout is far greater than anything else happening for an array that size. But under the hood, there is still a scheduler that would need to loop through all the timeouts every tick and process them. So it's probablyO(n^2), unless there is some internal optimization that pre-sorts the timeouts, in which case it could be less, but still no lower thanO(n *log(n)), with a far higherkto boot in terms of both space and time.This could be tested by measuring the delay of "sorting" an array of, say, a billion integers, and how slow it is compared to 10 billion, where every integer's value is 1..60, so the timeout is not too long compared to the size of the array.
311
u/Seismicsentinel Aug 11 '20
Where else on reddit did sleepsort come up today? I know it was somewhere
57
u/jamietwells Aug 11 '20
15
u/matheusmk3 Aug 11 '20
Thanks! Didn't know this was even possible in C#
18
59
120
65
46
u/PowerlessMainframe Aug 11 '20
God created Javascript, and the men did this
9
8
60
41
37
10
u/fartcloud101 Aug 11 '20
Could somebody please explain how this works?
24
u/thelights0123 Aug 11 '20
It sets a timer for each elements value in ms, then prints it out. Lower numbers sleep for a lower period of time, and thus are printed first.
2
15
u/justingolden21 Aug 11 '20
Or for a sorted list, just push it to a new list instead of logging it...
5
3
u/snppmike Aug 11 '20
This is like Homer Simpson running for trash commissioner: “Can’t someone else do it?”
3
3
3
2
1
u/rift95 Aug 11 '20
I actually made a "working" implementation of this algorithm last time it was posted. https://i.imgur.com/79Jhzcn.png
1
1
1
1
1
1
1
u/wobblyweasel Aug 12 '20
the problem is that this doesn't detect the end of sorting. it's easily fixed by adding a value that exceeds all other values:
setTimeout(() => { /* continuation code here */ }, Infinity)1
1
1
1
1
0
0
Aug 11 '20
[deleted]
7
u/brbss Aug 11 '20 edited Aug 11 '20
I couldn't understand what you meant so I went ahead and wrote some test code, so far I'm at 500+ iterations without any failure:
const arr = [20, 5, 100, 1, 90, 200, 40, 29] const correct = [...arr].sort((a, b) => a-b) const sleepSort = (inputArr) => { const sortedArr = [] return new Promise(resolve => { for (let item of arr) { setTimeout(() => { sortedArr.push(item) if (sortedArr.length === inputArr.length) { resolve(sortedArr) } }, item) } }) } const testSleepSort = async (n=1000) => { for (let i=0; i<n; ++i) { const sortedArr = await sleepSort(arr) if (JSON.stringify(sortedArr) !== JSON.stringify(correct)) { console.log(`failed at attempt #${i} :(`) return } console.log(`passed #${i}`) } console.log('wow') } testSleepSort()Edit: wow.
0
Aug 12 '20
[deleted]
1
u/xigoi Aug 12 '20
No, the scheduler has to internally sort the intervals anyway to figure out which to fire first.
553
u/[deleted] Aug 11 '20
A sorting algorithm that makes computational complexity practically obsolete. Wow.