Sorting Algorithms.

[laingsoft]

What's your favorite?

Mine is obviously sleepsort.

http://www.cs.princeton.edu/courses/arc ... 2Tries.pdf

 

[ttsgeb]

My God, sleepsort is beautiful. I just... It's so perfect.

 

[grossaffe]

sleepsort makes me want to cry.

I'm a fan of heapsort for being simple, very fast, and low memory requirement. Mergesort is great for also being very fast and can be made parallel for a speed boost in multi-core systems.

 

[laingsoft]

Heapsort is really a beautiful algo. When I first wrote my heap implementation for a data structures class, our prof didn't mention it until well after we had finished. At that point she was like "So, now if you dump everything out of your heap, do you notice anything about the data?" I do love it.

Mergesort always irked me for some reason. Maybe it's the recursion. I just always leaned more towards quicksort. Usually when I have to sort something I end up using quicksort rather than mergesort if the language doesn't have a built in sort function.

 

[grossaffe]

Heapsort is really a beautiful algo. When I first wrote my heap implementation for a data structures class, our prof didn't mention it until well after we had finished. At that point she was like "So, now if you dump everything out of your heap, do you notice anything about the data?" I do love it.

Mergesort always irked me for some reason. Maybe it's the recursion. I just always leaned more towards quicksort. Usually when I have to sort something I end up using quicksort rather than mergesort if the language doesn't have a built in sort function.

quicksort has the issue of being an O(N^2) function, however I have made use of it in my laziness since it's built into C's stdlib.

 

[laingsoft]

It's only ever O(n^2) if the list is already sorted and you don't choose the pivot properly. But yeah I guess.

We are pretty spoiled with libraries

 

[grossaffe]

It's only ever O(n^2) if the list is already sorted and you don't choose the pivot properly. But yeah I guess.

We are pretty spoiled with libraries

It's always O(N^2) because "Big O" notation specifies worst-case scenario. The average case is nlog(n) like the other sorting algorithms, though. Kinda like heap insertion is O(nlog(n)) but its average case is actually a constant (at least I think it was the insertion that was a constant at about 2 percolations no matter the size of the heap).

 

[laingsoft]

Ah, Well it was a long time since I did my algorithms course, you are right.

And I believe heap insertion worst case is O(logN) not O(N logN), and deletions are also O(LogN)

 

[grossaffe]

Ah, Well it was a long time since I did my algorithms course, you are right.

And I believe heap insertion worst case is O(logN) not O(N logN), and deletions are also O(LogN)

I do believe you are correct. I think I had nlog(n) in my head from the sorting.

 

[grossaffe]

My brother is a fan of the slow sort.