Sorting Algorithms

[COLOR="Red"]My prof. finished his 2 part lecture on sorting algorithms. Then he showed us this web page:

Sorting Algorithms

I am amazed. Click on them to see the animation work.[/COLOR]

Assuming the animations reflect time consumption... is there any reason to use one other than Quick Sort?

But other than my mass confusion, this is pretty cool.

Seen these before. They're cool.

I made one of my own for an avatar once:


In their particular visualization... quick sort looks really fast because they do multiple swaps in one animation frame. It is probably the fastest in practice, but not by as much as it looks. (Until you're sorting 100000+ things. Then it is.)

I've always liked Bubble Sort. It has a cute name and it's the easiest to learn. I had to do a presentation in class for Merge Sort about two years ago.

Quick Sort was a pain in the ass to learn in the beginning. I don't remember how Selection does it's thing.

[video=youtube;t8g-iYGHpEA]http://www.youtube.com/watch?v=t8g-iYGHpEA[/video]

[video=youtube;iXAjiDQbPSw]http://www.youtube.com/watch?v=iXAjiDQbPSw[/video]

c

[COLOR="Red"]

c

Super cool![/COLOR]

Assuming the animations reflect time consumption... is there any reason to use one other than Quick Sort?

If you are able to make certain assumptions about the data to be sorted (such as that they are all integers from 1 to 100), you can use a faster sorting algorithm like bucket sort. Basically you can just count how many times each number occurs and then make the sorted list based on the count.

Assuming the animations reflect time consumption... is there any reason to use one other than Quick Sort?

Does not reflect time consumption.

A combination of Mergesort and Quicksort is usually done whenever you do a sort in java, python, c or any other language really.

For integers, radix sort is quite fast. For partly sorted arrays, smoothsort is the way to go. As Spaz said, what algorithm you decide to use depends on the constraints you have.

For partly sorted arrays, smoothsort is the way to go.

Smoothsort is so cool.

What I don't understand about insertion sort, as presented in the original link, is...

Why go back in descending order? Would it not be faster to cut the sorted in half every time by comparing it to the middle element, using log(sorted) instead of linear(sorted) time?


I guess it's a data structure thing? If your sorted data's in a simple array, you need to move all the elements anyway. But if it's in something different where insertion's O(1) then using a log time to find the point seems better.

I don't know of any sequential data structure for which both insertion and random access (which is needed for the binary search you're describing) are O(1).

So assuming both ways of insertion sort are O(n^2)y its only real use is as a way to sort small data sets that is very simple to implement from scratch, so saving some time on the comparisons might not be worth complicating things when you could just use a better algorithm instead.

I don't know of any sequential data structure for which both insertion and random access (which is needed for the binary search you're describing) are O(1).

Fibonacci-heaps does that I think. (Messy though)

I don't know of any sequential data structure for which both insertion and random access (which is needed for the binary search you're describing) are O(1).

As long as they're under O(n) it helps... they could be log(n) or n^0.5 and it would be better than doing it linearly.



If it was in a tree with fast insertion you'd get both in O(log(n)) for example, as long as the height of the tree ~ log(n).


Then you go through n points with O(log(n)) to insert each, overall O(n logn), which matches single threaded quicksort. Not sure how feasible it is to make a thread safe tree for insertion only. If it is possible then you should get O(log n) sorting with n processors.