What the heck is sleep sort anyway?
Computer science students are probably familiar with terms quick sort, merge sort, insertion sort, and the simplest of them all, bubble sort. But a new player has joined the game; his name is sleep sort.
Dubbed as “King of Laziness”, it became popular after a post on 4Chan’s programming board. I have to admit, it falls under the “Wow, I never thought about it that way” kind of algorithm.
The idea is simple: for each number x in an array, start a timer for x seconds. When that timer runs out, print x.
For example: We have an array of whole numbers [2,4,3,1].
So there are four timers: one for each number in the array.
Let’s start counting while keeping track of those timers.
+----------------+-------------------+
| | time(s) |
| +---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 |
+-------+--------+---+---+---+---+---+
| | Timer2 | 2 | | | | |
| +--------+---+---+---+---+---+
| | Timer4 | 4 | | | | |
| value +--------+---+---+---+---+---+
| | Timer3 | 3 | | | | |
| +--------+---+---+---+---+---+
| | Timer1 | 1 | | | | |
+-------+--------+---+---+---+---+---+
Okay, so we have the initial values for the timer at 0th second.
Now let’s move forward 1 second.
+----------------+-------------------+
| | time(s) |
| +---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 |
+-------+--------+---+---+---+---+---+
| | Timer2 | 2 | 1 | | | |
| +--------+---+---+---+---+---+
| | Timer4 | 4 | 3 | | | |
| value +--------+---+---+---+---+---+
| | Timer3 | 3 | 2 | | | |
| +--------+---+---+---+---+---+
| | Timer1 | 1 | 0 | | | |
+-------+--------+---+---+---+---+---+
What happened here? So all the values are decremented by 1.
Since timer1 has run out, print the value of 1. So, “1”.
What happens next?
+----------------+-------------------+
| | time(s) |
| +---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 |
+-------+--------+---+---+---+---+---+
| | Timer2 | 2 | 1 | 0 | | |
| +--------+---+---+---+---+---+
| | Timer4 | 4 | 3 | 2 | | |
| value +--------+---+---+---+---+---+
| | Timer3 | 3 | 2 | 1 | | |
| +--------+---+---+---+---+---+
| | Timer1 | 1 | 0 | | | |
+-------+--------+---+---+---+---+---+
Timer2 has run out, so print the value of 2. So “1, 2”
Then,
+----------------+-------------------+
| | time(s) |
| +---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 |
+-------+--------+---+---+---+---+---+
| | Timer2 | 2 | 1 | 0 | | |
| +--------+---+---+---+---+---+
| | Timer4 | 4 | 3 | 2 | 1 | |
| value +--------+---+---+---+---+---+
| | Timer3 | 3 | 2 | 1 | 0 | |
| +--------+---+---+---+---+---+
| | Timer1 | 1 | 0 | | | |
+-------+--------+---+---+---+---+---+
Timer3 ran out, so print the value of 3. “1, 2, 3”
You get the idea. The next printed number is 4. So “1, 2, 3, 4”. Sorted!. Applause.
So how do we do that in Javascript?
Javascript has a neat function, setTimeout(), that lets us delay the execution of a function. The full syntax is
setTimeout((arg1, arg2,...) => {
//body of function
//do something
}, delay_in_miliseconds)
We got the timer, what else?
We need to iterate through the array. We can use the forEach() here.
Lastly, we need to wrap them in a function.
From the top. The function takes in an array. So we have
const sleepsort = array => {
//function body
}
Now we need to iterate though that array. So we now have
const sleepsort = array => {
array.forEach(number => {
//set the timer here
})
}
For each (hehe, see the pun there?) number, set a timer of ‘number’ seconds.
const sleepsort = array => {
array.forEach(number => {
setTimeout(() => {
//do something here
}, number)
})
}
When the timer runs out, print that number. Finally, we have
const sleepsort = array => {
array.forEach(number => {
setTimeout(() => {
console.log(number)
}, number)
})
}
Done!
Let’s feed it some numbers. Say [8, 9, 7, 6, 5, 4, 3, 2, 1, 10].
Open Chrome’s Javascript console by pressing F12.
Copy-paste the code above.
Put the array into a variable.
Lastly, call the function with the array as the argument.
And the output will be:
1
2
3
4
5
6
7
8
9
10
Boom! Sorted.
You can also change the console.log() into arr.push() where arr is an empty array. Then return the array.
.
Thanks for reading 🙂
![[Social Account]](https://krishnarowterhome.files.wordpress.com/2019/02/krishna-rowter-quora.png){kind=small}
A Programming Journal 
Leave a comment