[Tutor] sorting algorithm

[Steven D'Aprano]

On Thu, 4 Mar 2010 04:34:09 am Glen Zangirolami wrote:
> http://www.sorting-algorithms.com/
>
> It is a fantastic website that explains each kind of sort and how it
> works. They also show you visuals how the sorts work and how fast
> they go based on the amount of data.

For actual practical work, you aren't going to beat the performance of 
Python's built-in sort. Unless you are an expert, don't even think 
about trying. If you are an expert, you've surely got better things to 
do.


> Depending on the amount/kind of data I would choose a sorting
> algorithm that fits your needs.
>
> Bubble sorts tends to get worse the larger the data set but can be
> very useful to sort small lists.

Bubble sorts are useless for any real work. They are a shockingly bad 
way of sorting anything beyond perhaps 4 or 5 items, and even for lists 
that small there are other algorithms which are barely more complicated 
but significantly faster.

Bubble sorts not only get slower as the list gets bigger, but they do so 
at an every increasing rate: let's say it takes 1 second to sort 100 
items (for the sake of the argument). Then it will take:

4 seconds to sort 200 items
9 seconds to sort 300 items
16 seconds to sort 400 items
25 seconds to sort 500 items
36 seconds to sort 600 items
...

and so forth. In other words, multiplying the number of items by a 
factor of X will multiply the time taken by X squared.

The only advantage of bubble sort is that the algorithm is easy to code. 
Otherwise it is horrible in just about every imaginable way.



-- 
Steven D'Aprano