sort functions in python

[t3chn0n3rd]

Do you think it is relatively easy to write sort algorithms such as
the common Bubble sort in Python as compared to other high level
programming langauges

[Michael Spencer]

t3chn0n3rd wrote:

Do you think it is relatively easy to write sort algorithms such as
the common Bubble sort in Python as compared to other high level
programming langauges

yes

[Jeff Schwab]

Steven D'Aprano wrote:

On Fri, 08 Feb 2008 17:00:27 -0800, t3chn0n3rd wrote:

>Do you think it is relatively easy to write sort algorithms such as the
common Bubble sort in Python as compared to other high level programming
langauges

You realise that bubble sort is one of the worst possible sort algorithms
possible, particularly on modern hardware? It's not the worst: bogo sort
and bozo sort are worse, but bubble sort is still pretty atrocious.

That's the conventional wisdom, mostly because CS professors need a "bad
algorithm" to show undergrads, but it's not really accurate. The truth
is that bubble-sort's performance depends strongly on the input data.
In the worst case, yes, bubble-sort is O(n^2); however, for
almost-sorted data (only a few elements out of place), bubble-sort is
actually one of the fastest known algorithms. For already-sorted data,
bubble-sort is O(n). If you expect your data to be pretty nearly sorted
already, but you just want to make sure (e.g. because a small number of
elements may have been inserted or removed since the last sort),
bubble-sort is a good choice.

[Carl Banks]

On Feb 9, 4:37 pm, Jeff Schwab <[e-mail]:

Carl Banks wrote:

On Feb 8, 10:09 pm, Jeff Schwab <[e-mail]:

If you expect your data to be pretty nearly sorted
already, but you just want to make sure (e.g. because a small number of
elements may have been inserted or removed since the last sort),
bubble-sort is a good choice.

But if you're at that stage you probably were doing something wrong in
the first place.

How do you figure?

"Probably."

:)
Carl Banks

[Hrvoje Niksic]

Steven D'Aprano <st***@REMOVE-THIS-cybersource.com.auwrites:

>I've never seen anything better than bubble sort being called
bubble sort.

What, you didn't read the post you're replying to?

I responded to a specific point about combsort being called bubble
sort. I agree that generally the line between "bubblesort variants"
and "algorithms based on bubblesort" is blurry and drawn by convention
rather than any strict criterion.