Have you heard of “sleep sort” algorithm? I recently came across it while searching for the most out of the box algorithms on the internet. So I decided to implement this in c plus plus and try it by myself. In this tutorial, we will implement this algorithm in c plus plus. While doing so, we’ll learn:

1. How to multi-thread in c plus plus
2. How to generate random numbers in c plus plus
3. How to compile the code in Linux
4. Use of std::shared_ptr and std::make_shared()

The algorithm is quite simple and can be described in just one line: For every element x in the unsorted list A, start a program that sleeps for x duration of time and prints x after that. Did you get it ? Let’s see the pseudo code for it.

pseudo_code

function sleep_and_print(x):
sleep(x)
print x

function sleep_sort(A):
for every x in list A:


Although the pseudo code seems simple. However, multi-threading part makes it a bit tricky. So, let’s dive into the implementation of this algorithm in c plus plus.

sleep_sort.cpp

#include <iostream>
#include <vector>
#include <time.h>

static const int num_threads = 20;
void sleep_and_print(int x)
{
// sleep for time x
std::cout<<x<<" ";
}

int main() {

srand(time(NULL));
std::vector<int> num_list;
std::cout<<std::flush;
std::cout<<"Unsorted list: "<<std::endl;

for(size_t i = 0; i< 20; i++)
{
int num = int(rand()%100);
std::cout<<num<<" ";
num_list.push_back(num);
}

for (int i = 0; i < num_list.size(); ++i) {
}

std::cout << "\nSorted list: \n";

//Join the threads with the main thread. This will execute all the function calls
//parallely
for (int i = 0; i < num_threads; ++i) {
}

return 0;
}


Compiling the code in Linux:

$g++ -std=c++11 -pthread sleep_sort.cpp -o sleep_sort  And here is the output: $ ./sleep_sort
Unsorted list:
19 24 19 63 97 36 67 9 5 67 7 84 33 87 20 88 67 40 78 94
Sorted list:
5 7 9 19 19 20 24 33 36 40 63 67 67 67 78 84 87 88 94 97