In this example, you will learn to implement sleep sort or lazy sort algorithm in c++. In this algorithm we create different threads for each of the elements in the input array and then each thread sleeps for an amount of time which is proportional to the value of corresponding array element.
Hence, the thread having the least amount of sleeping time wakes up first and the number gets printed and then the second least element and so on. The largest element wakes up after a long time and then the element gets printed at the last. Thus the output is a sorted one.
All this multithreading process happens in background and at the core of the OS. We do not get to know anything about what’s happening in the background, hence this is a “mysterious” sorting algorithm.
Sleep Sort Functions:
_beginthread() is a C run-time library call that creates a new ‘thread’ for all the integers in the array and returns that thread.Each of the ‘thread’ sleeps for a time proportional to that integer and print it after waking.
We pass three parameters to _beginthread :
- start_address –> start address of the routine/function which creates a new thread
- stack_size –> Stack Size of the new thread (which is 0)
- arglist –> Address of the argument to be passed
The return value of _beginthread() function is a handle to the thread which is created. So we must accept is using the datatype- ‘HANDLE’ which is included in windows.h header ‘HANDLE’ datatype is used to represent an event/thread/process etc So ‘HANDLE’ datatype is used to define a thread We store the threads in an array – threads which is declared using ‘HANDLE’ datatype.
WaitForMultipleObjects() is a function that processes the threads and has four arguments:
- no_of_threads –> Number of threads to be processed
- array_of_threads –> This is the array of threads which should be processed. This array must be of the type ‘HANDLE’
- TRUE or FALSE –> We pass TRUE if we want all the threads in the array to be processed
- time_limit –> The threads will be processed until this time limit is crossed. So if we pass a 0 then no threads will be processed, otherwise if we pass an INFINITE, then the program will stop only when all the threads are processed. We can put a cap on the execution time of the program by passing the desired time limit.
To implement sleep sort, we need multithreading functions, such as _beginthread() and WaitForMultipleObjects(). Hence we need to include windows.h to use these functions. This program will not work on any online IDE. We must run it in your PC.
Note: this code is for WINDOWS and not for LINUX.
// This is the instruction set of a thread
// So in these threads, we "sleep" for a particular
// amount of time and then when it wakes up
// the number is printed out
void routine(void *a)
int n = *(int *) a; // typecasting from void to int
// Sleeping time is proportional to the number
// More precisely this thread sleep for 'n' milliseconds
// After the sleep, print the number
void sleepSort(int arr, int n)
// An array of threads, one for each of the elements
// in the input array
// Create the threads for each of the input array elements
for (int i = 0; i < n; i++)
threads[i] = (HANDLE)_beginthread(&routine, 0, &arr[i]);
// Process these threads
WaitForMultipleObjects(n, threads, TRUE, INFINITE);
// Main function
// Doesn't work for negative numbers
cout<<"Enter the size of array elements: ";
cout<<"Enter "<<n<<" elements:"<<endl;
for(i = 0; i < n; i++)
i = sizeof(arr) / sizeof(arr);
sleepSort (arr, n);
When you run the program, the output will be following:
Enter the size of array elements: 5
Enter 5 elements:
1 2 3 5 8
The overall time complexity can be assumed as O(NlogN + max(input)), where, N = number of elements in the input array, and input = input array elements