Comparing sorting algorithms

[Insectoid]

Found this neat page that visually shows how different sorting algorithms work, as well as letting you compare the speeds of different algorithms.

http://cg.scs.carleton.ca/~morin/misc/sortalg/

[Alexmula]

nice! what is the point of bozosort and how does it work? seems highly unefficient

[Insectoid]

A lot of these are inefficient. The qsort (quicksort) and jsort are the fastest. permsort is very slow (checks every permutation of the list and checks if that permute is in order). It's probably the slowest one guaranteed to find it eventually. I think bozosort is the one that randomly swaps 2 elements and checks if the list is in order.

[Superskull85]

http://en.wikipedia.org/wiki/Bozo_sort

"Its only use is for educational purposes, to contrast it with other more realistic algorithms. If bogosort were used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, one would throw the deck into the air, pick the cards up at random, and repeat the process until the deck is sorted."

List of sorting algorithms: http://en.wikipedia.org/wiki/Sorting_algorithms

[Insectoid]

Woops, the merge sort is actually the fastest on the page.

[Tony]

QuickSort is interesting to study in detail because while "Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms" (faster than merge sort), there are cases where it can perform as bad as O(n^2).

There are other things to consider, such as available space or memory, and ease of implementation.

Ultimately, for specific types of data and systems, certain sort algorithms perform better than others. You could likely go faster than a generic quicksort/mergesort if you were to know some information about what kind of data you are sorting (structure, patterns, etc).

[Brightguy]

Tony @ Sun Nov 08, 2009 2:08 am wrote:

QuickSort is interesting to study in detail because while "Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms" (faster than merge sort), there are cases where it can perform as bad as O(n^2).

If you enforce a good pivot (say, the median) then quicksort has Θ(nlogn) worst-case runtime.

Always pivot on the first element and quicksort will take Θ(n²) to sort a pre-sorted list.