Sleep Sort Algorithm: The Algorithm that sleeps to do work!

There are many sorting algorithms out there. But there are some special which makes them unique with their logic. Sleep Sorting Algorithm is such one. Kindly note that this may not have any real world implementation as the time complexity is very high for this.

What is Sorting?

Sorting is a way of arranging a group of things in a specified order. Normally, the order is a “natural order.” Examples of natural orders are counting order or alphabetical order. In computing, time and memory usage are of concern when sorting. Some algorithms are very fast, but use a lot of memory, or vice versa. Usually, speed has higher priority. The speed of an algorithm is often determined by the number of compares and/or swaps required.

Sleep Sort Algorithm:

The basic idea of sleep sort is to print the number i,after i seconds (or time units).

The pseudocode for sleep sort is:

procedure printNumber(n)

sleep n seconds

print n

end

for arg in args

run printNumber(arg) in background

end

wait for all processes to finish

Sleep Sort Algorithm

For example, if the numbers to be sorted are 5, 3, 9:
Print 5 after 5 seconds;
Print 3 after 3 seconds; and
Print 9 after 9 seconds.

and woah, you realize that you get a sorted output!

For Layman:

Let us try and understand sleep sort through an example.  Assume that Ankit has 5 balloons. Each balloon has a number written on it, and each number belongs to the following set – {1,4,2,6,5}.  Now,  Ankit gives the balloons to 5 people, such that each person gets a single balloon. He instructs each person to “sleep” for ‘n’ number of seconds, where n is the number written on the respective person’s balloon, and tells the person to come and give him the balloon after he has finished “sleeping”. So, if a person receives a balloon with the number ‘4’ written on it, then he has to sleep for 4 seconds, and then give the balloon back to Ankit. So, in what order will Ankit receive the balloons?  He will first receive the balloon with the number ‘1’ on it, then the one with ‘2’.. and so on. Thus, the order in which he will receive the balloons will be the sorted order.

Sleep Sorting Ballons

For Programmers:

Talking from a programmer’s perspective, for an array with elements a1, a2…an , threads th1,th2….thn are created. A thread thi is made to sleep for ai seconds. When the thread thi wakes up, ai is printed. Therefore, in the end, all the numbers are printed in the sorted order.

The Downside:

Though the practicality of sleep sort is a big question, it certainly is a very inventively thought algorithm. Suppose a guy enters two number 9999 and 1 to be sorted. 1 will be printed in a sec, whereas you have to wait 9999 secs to get 9999 to get printed. It takes total of 10000 secs to just sort two numbers.

Implementation:

Here is Sample code in C

#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
 
int main(int c, char **v)
{
        while (--c > 1 && !fork());
        sleep(c = atoi(v[c]));
        printf("%d\n", c);
        wait(0);
        return 0;
}

Here is Sample code in Java(1.5+):

import java.util.concurrent.CountDownLatch;
 
public class SleepSort {
	public static void sleepSortAndPrint(int[] nums) {
		final CountDownLatch doneSignal = new CountDownLatch(nums.length);
		for (final int num : nums) {
			new Thread(new Runnable() {
				public void run() {
					doneSignal.countDown();
					try {
						doneSignal.await();
 
						//using straight milliseconds produces unpredictable
						//results with small numbers
						//using 1000 here gives a nifty demonstration
						Thread.sleep(num * 1000);
						System.out.println(num);
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
				}
			}).start();
		}
	}
	public static void main(String[] args) {
		int[] nums = new int[args.length];
		for (int i = 0; i < args.length; i++)
			nums[i] = Integer.parseInt(args[i]);
		sleepSortAndPrint(nums);
	}
}

Click here for Source Code for Sleep Algorithm in Various languages

Click here to read more about sorting on wiki.

Here is list of various sorting algorithms out there:

  1. Bead sort
  2. Bogosort
  3. Bubble sort
  4. Circle Sort
  5. Cocktail sort
  6. Comb sort
  7. Counting sort
  8. Cycle sort
  9. Gnome sort
  10. Heapsort
  11. Insertion sort
  12. Merge sort
  13. Pancake sort
  14. Patience sort
  15. Permutation sort
  16. Quicksort
  17. Radix sort
  18. Selection sort
  19. Shell sort
  20. Sleep sort
  21. Stooge sort
  22. Strand sort
  23. Tree sort on a linked list

Hope you found this algorithm interesting. Let me know if you came across any such algorithms in comments.

Pravin Hanchinal

Pravin Hanchinal is a Professional Speaker, Educator, Edupreneur, Entrepreneur,Big Data,IoT and Cloud Evangelist.Trained around 7500+ people which include teachers, students, industry on recent technologies. Though passionate about being a technical coach, educator but his hunger for learning never stops. Long way ahead, yet to accomplish a lot for this proud son of a agriculturist. He is available for conducting workshop for students, faculty, industry and general audiences. In Nutshell: Sapiosexual, Edupreneur, FOSS, Cloud and Big Data Evangelist

You may also like...

Leave a Reply