Sleep sort: A sorting algorithm without compare
Table of Contents
Disclaimer
I'm not inventing this algorithm. I saw a picture of a Javascript version of this algorithm in my feed and love it. So, I try to implement this in Swift. This algorithm is meant to be a joke; don't take it seriously.
You can easily support sarunw.com by checking out this sponsor.
Debug 10x faster with Proxyman: Your ultimate tool to capture HTTPs requests/ responses, natively built for your iPhone and macOS. Special deal for Black Friday: Get 30% off for all Proxyman licenses with code “BLACKFRIDAY2024”.
Sorting without compare
Every sorting algorithm I have seen so far have one thing in common, elements that you want to sort have to be comparable. That means if you pick any two elements from an array, it must be a way to tell which comes before. In Swift, we use Comparable protocol.
What if I tell you that there is a sorting algorithm that doesn't require elements in a collection to be comparable.
That's the beauty of this sorting algorithm, an algorithm without compare, Sleep Sort.
Sleep Sort
Here is the implementation of Sleep sort.
extension Array where Element == Int {
func sleepSorted() -> [Element] {
var sortedElements = [Element]()
let group = DispatchGroup() // <1>
for element in self {
group.enter()
DispatchQueue.global().async {
sleep(UInt32(element)) // <2>
print(element)
sortedElements.append(element) // <3>
group.leave()
}
}
group.wait() // <4>
return sortedElements
}
}
<1> We create a dispatch group because we want to wait for all elements to wake up before continuing execution.
<2> Put each element to sleep.
<3> After wake up, put an element in a sorted array.
<4> After every element are waking up, we return sortedElements
Limitation
It quite fun to think of the limitation of this funny algorithm. I only come up with one limitation so far.
The elements can't be too close together
The difference between each element after convert to time can't be smaller than the operation cost for sleep and asynchronous operation. Let's say the operation cost of each asynchronous operation varies from 0 to 1 second (It needs at most one second between each asynchronous method is one second). The difference can't be smaller than 1.
For example, an array of [0.5, 0.6, 0.7]. The difference between these elements is less than 1.
We want them to sleep at the same time, but because asynchronous operation, which varies from 0 to 1 second, they might not start at the same time and might not wake up immediately.
0.5 start sleep at 0.5 and finish at 1
0.6 start sleep at 0.1 and finish at 0.7
0.7 start sleep at 0.7 and finish at 1.4
So the result is wrong in this case [0.6, 0.5, 0.7]
If the elements are different are larger than 1, this will be fine.
For example, an array of [5, 6.1, 7.2]
5 start sleep at 0.5 and finish at 5.5
6.1 start sleep at 0.1 and finish at 6.2
7.2 start sleep at 0.7 and finish at 7.9
Optimization
We usually measure the performance of an algorithm by Big O Notation, but time complexity measure by Big O Notation is measure relative to the number of input, not the value of the input, so I don't think Big O Notation can apply in this case.
In this case, time complexity would vary on the maximum number of values in an array. We can optimize the runtime by trying to lower these values down.
extension Array where Element == Int {
func sleepSorted() -> [Element] {
var sortedElements = [Element]()
let group = DispatchGroup()
for element in self {
group.enter()
DispatchQueue.global().async {
let ms = 1000
usleep(useconds_t(element * ms))
print(element)
sortedElements.append(element)
group.leave()
}
}
group.wait()
return sortedElements
}
}
Instead of sleep()
, which suspend execution in a second interval, we use usleep
, which sleeps in millisecond interval.
usleep()
take a parameter of microsecond intervals (1 second equals 1,000,000 microseconds).
Conclusion
I can't tell it is a stupid or genius algorithm, but it sure got a beauty in it. I hope you enjoy the article.
You can easily support sarunw.com by checking out this sponsor.
Debug 10x faster with Proxyman: Your ultimate tool to capture HTTPs requests/ responses, natively built for your iPhone and macOS. Special deal for Black Friday: Get 30% off for all Proxyman licenses with code “BLACKFRIDAY2024”.
Related Resources
Read more article about Swift, Funny, Sort, or see all available topic
Enjoy the read?
If you enjoy this article, you can subscribe to the weekly newsletter.
Every Friday, you'll get a quick recap of all articles and tips posted on this site. No strings attached. Unsubscribe anytime.
Feel free to follow me on Twitter and ask your questions related to this post. Thanks for reading and see you next time.
If you enjoy my writing, please check out my Patreon https://www.patreon.com/sarunw and become my supporter. Sharing the article is also greatly appreciated.
Become a patron Buy me a coffee Tweet ShareAnimation delay and repeatForever in SwiftUI
Explore how delay and repeatForever affect an animation.
Easy way to detect a retain cycle in a view controller
A view controller is one component where memory leak usually takes place since it holds many pieces together. One of the easiest ways to detect them is to see if a view controller is not being deallocated. Let's see how Xcode breakpoint can help you find a leak.