wood burning stoves 2.0*
The moose likes Meaningless Drivel and the fly likes New sort algorthim Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "New sort algorthim" Watch "New sort algorthim" New topic
Author

New sort algorthim

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11402
    
  16

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)


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

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!

[Jess in Action][AskingGoodQuestions]
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11402
    
  16

perhaps I mis-understand what you're saying, but (0,1,98234234) would still take a while, no?
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

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
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18650
    
    8

That's a pigeonhole sort, with an infinite number of pigeonholes.
Paul Anilprem
Enthuware Software Support
Ranch Hand

Joined: Sep 23, 2000
Posts: 3312
    
    7
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.


Enthuware - Best Mock Exams and Questions for Oracle/Sun Java Certifications
Quality Guaranteed - Pass or Full Refund!
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18650
    
    8

Not to mention that it doesn't work so well if there are negative numbers in the set being sorted.
Mark Spritzler
ranger
Sheriff

Joined: Feb 05, 2001
Posts: 17257
    
    6

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


Perfect World Programming, LLC - Two Laptop Bag - Tube Organizer
How to Ask Questions the Smart Way FAQ
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.

Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4659
    
    5

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
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
And I agree with Pat on all points, especially the last.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11402
    
  16

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
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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
Bartender

Joined: Oct 02, 2003
Posts: 11402
    
  16

Here's what I get

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

Joined: Sep 30, 2010
Posts: 290

I don't think this should be in the Meaningless Drivel.
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4659
    
    5

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
Bartender

Joined: Oct 02, 2003
Posts: 11402
    
  16

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
Bartender

Joined: Oct 02, 2003
Posts: 11402
    
  16

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
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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

Joined: Sep 30, 2010
Posts: 290

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

Joined: Sep 30, 2010
Posts: 290

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
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.
Suhrid Karthik
Ranch Hand

Joined: Aug 31, 2008
Posts: 58

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
 
permaculture playing cards
 
subject: New sort algorthim