At 6/28/09 06:05 AM, GustTheASGuy wrote:
At 6/28/09 03:16 AM, Toast wrote:
I've been trying to find an algorithm that can sort lists of n items in n steps, but so far no success xD
Uhuh.
I think it's impossible to do that, because to answer the question "Is this list of n items sorted?" you need n comparisons, and therefore writing a stable general sort that sorts lists from scratch in n or less steps would be to answer P = NP. Now of course it may be possible that P = NP, but what is not possible is that I can solve it :p
The best general sort is mergesort. O (n+klogn) where k+1 = number of first elements
The code I wrote is pretty much a merge sort. I was really impressed with the speed, i can give him 10 000 values to sort and it's gonna do it in a split second. Also I was wondering, is there any way to make your CPU work with full power on a problem? When I was trying to sort lists of 1 million values it was taking relatively a lot of time and my CPU didn't seem to work particularly hard on it.
Also, I see your point about not wanting to study. I just had a look at MIT open courseware's lectures on algorithms, in the first courses they don't do anything that I didn't learn on the internet in less than an hour. However I think that as things get more complex, it's bad to learn from the internet.
mergesort cmp = reduce . map return
where
reduce [xs] = xs
reduce xss = reduce (pair xss)
pair (xs:ys:xss) = merge xs ys : pair xss
pair rest = rest
merge (x:xs) (y:ys)
| cmp x y == GT = y : merge (x:xs) ys
| otherwise = x : merge xs (y:ys)
merge xs [] = xs
merge [] ys = ys
Interesting
Kay. Next spring or so then.
Oh. I'll have two weeks between coming from israel and going back to school. There's not so much to do around here, all you'll find is hi-tech companies like the INRIA. I know you like them, so if you'd like to visit the INRIA or something you can come here. I even have the email of the guy who's in charge of guiding the visitors.