-1
\$\begingroup\$

Just a fun puzzle which is inspired by following post in Quora:
What is the strangest sorting algorithm?

In nutshell, this sorting works by spawning a thread for each value "X", where the thread sleeps for "X" amount of time and then prints "X".

I could quickly implement using C++.

#include<cstdlib>
#include<chrono>
#include<iostream>
#include<thread>
#include<vector>

void SleepSort (const int i)
{
  std::this_thread::sleep_for(std::chrono::milliseconds(i));
  std::cout << i << " ";
}

int main (int argc, char** argv)
{
  std::cout << "Sorted array is:\n";
  std::vector<std::thread> threads;
  for(int i = 1; i < argc; ++i)
    threads.push_back(std::thread(SleepSort, std::atoi(argv[i])));

  for(auto& thread : threads)
    thread.join();
}

Test output:

./a.out 2 3 1 100 5 98 298 22 898
1 2 3 5 22 98 100 298 898

Questions:

  1. Can we do this for negative numbers as well?
    Actually I tried to add numeric_limit<int> and store the sleep timer in long. But then the sleep becomes too high.
  2. Can we make this program make still smaller in code size & better in performance?
\$\endgroup\$

closed as off-topic by Ethan Bierlein, Graipher, Mathieu Guindon May 19 '17 at 17:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Ethan Bierlein, Graipher, Mathieu Guindon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ There's not much point in trying to improve the performance of an algorithm that spends most of its time sleeping. \$\endgroup\$ – Edward May 19 '17 at 13:22
  • \$\begingroup\$ @Edward, how about making it sleep lesser and still perform the sorting properly. Of course, when so many threads are spawn, then talking about performance is naive :-). But let's think from user experience perspective. If the number's value is high then the sleep also will be high. In such case, the sorting will have to wait for that much longer. Is there a way by which we can reduce it. Nevertheless, the main issue is with the negative numbers. I think if we can solve that then automatically the performance should be solved. \$\endgroup\$ – iammilind May 19 '17 at 13:34
  • 3
    \$\begingroup\$ Solving the problem of sleep-sort with negative values means changing what your code does; this site helps changing how your code works. \$\endgroup\$ – Mathieu Guindon May 19 '17 at 17:24
4
\$\begingroup\$

This seems a rather trivial problem

  1. You have to gather all the inputs.

    std::vector<int> data;
    data.reserve(argc-1);
    for (int i = 1; i < argc; ++i)
        data.push_back(std::atoi(argv[i]));            
    
  2. You get the minimum value

    const int minElem = std::abs(*std::min_element(data.begin(), data.end()));
    
  3. You add the minElem as a second argument to your sleeper thread, so the first threat will start at 0 at earliest.

    void SleepSort (const int i, const int offset)
    {
        std::this_thread::sleep_for(std::chrono::milliseconds(i+offset));
        std::cout << i << " ";
    }
    
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.