Win a copy of Programming with Types this week in the Angular and TypeScript forum
or The Design of Web APIs in the Web Services forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Knute Snortum
  • Henry Wong
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Frits Walraven
  • Joe Ess
  • salvin francis

New sort algorthim

 
lowercase baba
Posts: 12784
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I came across this today - a sort algorithm i've never seen before:



so you read a number, fork off a process that sleep for that many seconds, then print the number.

you could probably sort a lot of small numbers rather fast, but you'd wait a while to sort (0,54232344)
 
author and iconoclast
Posts: 24203
43
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is cute! If you had an very precise timer, you could do one pass over the data to compute the smallest workable base interval, and then proceed as above. Linear-time sort with no space overhead!
 
fred rosenberger
lowercase baba
Posts: 12784
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
perhaps I mis-understand what you're saying, but (0,1,98234234) would still take a while, no?
 
Ernest Friedman-Hill
author and iconoclast
Posts: 24203
43
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, no benefit in computing different time intervals anyway -- why wouldn't you just always use the smallest one you can do? I should have thought a little more before posting
 
Marshal
Posts: 24837
60
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's a pigeonhole sort, with an infinite number of pigeonholes.
 
Enthuware Software Support
Posts: 4390
40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It doesn't look like any algorithm. It is seems to be just an obfuscated way to use an existing sorting algorithm implemented in the OS. You might as well call a sort function from a library, no?
Furthermore, if you have a smaller number at the end of the list, it might be printed out of order.
 
Paul Clapham
Marshal
Posts: 24837
60
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not to mention that it doesn't work so well if there are negative numbers in the set being sorted.
 
ranger
Posts: 17344
11
Mac IntelliJ IDE Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:Not to mention that it doesn't work so well if there are negative numbers in the set being sorted.



I think the developer that wrote that just figured out time travel. We shouldn't mock that genius. ;)

Mark
 
Rancher
Posts: 3412
34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ernest Friedman-Hill wrote:That is cute! If you had an very precise timer, you could do one pass over the data to compute the smallest workable base interval, and then proceed as above. Linear-time sort with no space overhead!


Well, I'm thinking all those forked processes take up some system resources somewhere. If you try to sort a million numbers with this, you might find that there's a bit more space overhead that originally considered.

Paul Anilprem wrote:It doesn't look like any algorithm. It is seems to be just an obfuscated way to use an existing sorting algorithm implemented in the OS.


Hm, I don't see how. What part is a sorting algorithm implemented in the OS? The call to sleep?

Paul Anilprem wrote:You might as well call a sort function from a library, no?


Sure, for any practical application, there are plenty of more reliable and efficient ways to do this. The point here is just that it's clever and different, just for fun.

Paul Anilprem wrote:Furthermore, if you have a smaller number at the end of the list, it might be printed out of order.


True, if we have a large enough number of arguments, and/or if we reduce the time interval enough. Also, if the user passes in floating-point numbers that are sufficiently close to each other in value.

 
Rancher
Posts: 4686
7
Mac OS X VI Editor Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mike Simmons wrote:Well, I'm thinking all those forked processes take up some system resources somewhere. If you try to sort a million numbers with this, you might find that there's a bit more space overhead that originally considered.



You think? If this was NCIS, Gibbs would smack the OP on the head.

Forking a process is cheap compared to having the user shoot the computer because your app is unresponsive, but its not free, and its only cheap when you look at Big OH notation, The two constants are fairly big. I could easily believe that each process take say 100 words of memory. If N is big, this becomes a serious problem.

Plus the overhead to create and join back a tread is far higher than that of comparing two integers or even two small strings.

But for MD, its perfect.
 
Mike Simmons
Rancher
Posts: 3412
34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mike Simmons wrote:

Paul Anilprem wrote:It doesn't look like any algorithm. It is seems to be just an obfuscated way to use an existing sorting algorithm implemented in the OS.


Hm, I don't see how. What part is a sorting algorithm implemented in the OS? The call to sleep?


Never mind - I thought about it some more and I think I agree. The part of the OS that determines when to resume each process is probably doing some sorting to schedule the wake-up calls. Oh well.
 
Mike Simmons
Rancher
Posts: 3412
34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And I agree with Pat on all points, especially the last.
 
fred rosenberger
lowercase baba
Posts: 12784
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wonder how you'd express this algorithm in Big-O notation...

O(magnitude of the largest element being sorted)???

and in my 30 seconds of testing, it does not work for floats, strings or even negative integers - although you could probably come up with some hash function to compensate for some/most/all those cases...

 
Mike Simmons
Rancher
Posts: 3412
34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

fred rosenberger wrote:I wonder how you'd express this algorithm in Big-O notation...

O(magnitude of the largest element being sorted)???


Yep.

fred rosenberger wrote:and in my 30 seconds of testing, it does not work for floats, strings or even negative integers - although you could probably come up with some hash function to compensate for some/most/all those cases...


Hmmm, this works fine with floats, on my system (MacBook Pro running OS x 10.6.7). Other than being vulnerable to error if two floats are very close to each other, as noted in my last post.

I did replace "wait" with "wait > /dev/null", to get rid of some annoying extra output.
 
fred rosenberger
lowercase baba
Posts: 12784
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's what I get

/export/home/hci/fbr1917>fred.sh 1 2.4 3
sleep: bad character in argument
2.4
1
3

 
Ranch Hand
Posts: 290
Debian Fedora Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't think this should be in the Meaningless Drivel.
 
Pat Farrell
Rancher
Posts: 4686
7
Mac OS X VI Editor Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

fred rosenberger wrote:I wonder how you'd express this algorithm in Big-O notation...
O(magnitude of the largest element being sorted)???



That is still O(1) since you have arbitrarily large constants A and B in the formula: time ~~ A + B * N
where N is the number of elements you are processing. Big-O is all about limits, so the actual values of A and B disappear.

Saying something is O(1) does not mean its faster than something O(N^2) for all values of N. Just that as N becomes really large, then it is safe to say T(N) < T(N^2)

 
fred rosenberger
lowercase baba
Posts: 12784
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know...it's been a while since I've done any big-0 notation calculations, but I would say this sort doesn't really work with it. I mean, assuming you ignore hardware and cpu limits - i.e. a machine with infinite memory and cpu cycles, you could sort one element or one trillion elements in 1 second - assuming all your input values were '1'.

However, sorting one element may take one second or 2^64 - 1 seconds, if your single input is 2^64 - 1.

The time is not dependent on the number of elements in any way I can see.
 
fred rosenberger
lowercase baba
Posts: 12784
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Arun Giridharan wrote:I don't think this should be in the Meaningless Drivel.


I think this is EXACTLY where this should be.

;-)
 
Mike Simmons
Rancher
Posts: 3412
34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It all depends on what parts you consider constant and what parts you consider variables. Big O analysis is typically carried out considering only N, the size of the input, as the thing that varies - but that needn't be the only variable that can be considered. And in this case, the max value of the input is far more significant than anything else, so have no problem saying the algorithm is O(max value) - that's far more useful and informative than saying O(1), IMO.

Actually I believe there is also an O(N) component to the execution time. It's just currently insignificant next to the O(1) component). But still, there's a loop in there that has to visit every element of the input once, parse it as a number, and start a new process for that input. If N were sufficiently large, and the wait time intervals were small enough, the O(N) could dominate over the O(1). Of course the algorithm would be failing badly at this point.
 
Arun Giridharan
Ranch Hand
Posts: 290
Debian Fedora Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mike Simmons wrote:

Actually I believe there is also an O(N) component to the execution time. It's just currently insignificant next to the O(1) component). But still, there's a loop in there that has to visit every element of the input once, parse it as a number, and start a new process for that input. If N were sufficiently large, and the wait time intervals were small enough, the O(N) could dominate over the O(1). Of course the algorithm would be failing badly at this point.



I'm not Clear with THIS.
 
Arun Giridharan
Ranch Hand
Posts: 290
Debian Fedora Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

fred rosenberger wrote:

Arun Giridharan wrote:I don't think this should be in the Meaningless Drivel.


I think this is EXACTLY where this should be.

;-)



Since it deals with Algorithm ,i don't feel it suits in Meaningless Drivel.
 
Mike Simmons
Rancher
Posts: 3412
34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, it's a very silly and inefficient algorithm, for fun only. I wouldn't put it in any of the "serious" forums. I suppose it might fit fine in Programming Diversions though.
 
Ranch Hand
Posts: 58
Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's a good one. By the way, it's called sleep sort and started off on 4chan. See this epic thread for a few laughs. It's also on wikipedia: Sleep_sort
 
Surfs up space ponies, I'm making gravy without this lumpy, tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!