Asp Forum - sort functions in python

t3chn0n3rd

2/9/2008 1:00:00 AM

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

18 Answers

Michael Spencer

2/9/2008 1:07:00 AM

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

2/9/2008 1:55:00 AM

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

http://www.codecodex.com/wiki/index.php?title=B...

Steven D'Aprano

2/9/2008 2:34:00 AM

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.

http://en.wikipedia.org/wik...

Frankly, you won't get better performance in Python than the built in
list.sort() method and sorted() function provide. If you want to actually
sort, use them.

But for the sake of the learning exercise, yes, Python makes it easy to
write algorithms including bubble sort and quick sort and merge sort.

Here's a version of bubble sort, from Wikibooks:

def bubblesort(l):
"Sorts l in place and returns it."
for passesLeft in range(len(l)-1, 0, -1):
for index in range(passesLeft):
if l[index] > l[index + 1]:
l[index], l[index + 1] = l[index + 1], l[index]
return l

http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/B...

--
Steven

Jeff Schwab

2/9/2008 3:09:00 AM

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.

Paddy

2/9/2008 6:13:00 AM

On 9 Feb, 01:00, t3chn0n3rd <darrin_al...@japan.com> 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

Hi,
From a quick google, you could compare the sources here:
http://www.daniweb.com/code/snipp...
with those from here:
http://cg.scs.carleton.ca/~morin/mis...

(It seems that sort routines are a favourite for showing off Java
applet capability).

- Paddy.
P.S. I also found this absolute gem: The intelligent design sort,
"works outside of time .."

http://www.dangermouse.net/esoteric/intelligentdesig...

:-)

Carl Banks

2/9/2008 6:27:00 AM

On Feb 8, 10:09 pm, Jeff Schwab <j...@schwabcenter.com> wrote:
> 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.

For a list of any decent size a few insertions using a bisection
algorithm will take fewer comparisons than a single bubblesort pass.

Carl Banks

Steven D'Aprano

2/9/2008 8:02:00 AM

On Fri, 08 Feb 2008 19:09:06 -0800, Jeff Schwab wrote:

> 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.

It depends on what you mean by "bubble sort". There are many different
variations of bubble sort, that are sometimes described by names such as
comb sort, cocktail sort, exchange sort, and sometimes merely referred to
bubble sort. It's rather like any divide-and-conquer sorting algorithm
being called quicksort.

I'm as guilty of that as anyone else -- the example code I posted, raided
from Wikibooks is very different from this bubble sort algorithm from
PlanetMath:

http://planetmath.org/encyclopedia/Bubbl...

def bubblesort(L):
done = False
while not done:
done = True
for i in xrange(len(L)-1):
if L[i+1] <= L[i]:
L[i], L[i+1] = L[i+1], L[i]
done = False
return L

This one runs significantly faster than the earlier one I posted.

Another vital factor is, what language are you implementing the sort
routine in? The conventional wisdom for low-level languages like assembly
and C doesn't necessarily hold for high-level languages like Python.
Comparisons are slow in Python and fast in C; in C a good algorithm will
minimize the amount of moves, while in Python a good algorithm will
minimize the number of comparisons.

Finally, what hardware are you running on? There are interactions between
hardware caches and pipes that can ruin the performance of an otherwise
promising algorithm.

But all those factors aside, I fear that your attempt to rehabilitate the
reputation of bubble sort is misplaced. Here's another person who wants
to defend bubble sort:

"A fair number of algorithm purists (which means they've probably never
written software for a living) claim that the bubble sort should never be
used for any reason. Realistically, there isn't a noticeable performance
difference between the various sorts for 100 items or less, and the
simplicity of the bubble sort makes it attractive."

http://linux.wku.edu/~lamonml/algor/sort/b...

But then on the same person's page on insertion sort:

"The insertion sort is a good middle-of-the-road choice for sorting lists
of a few thousand items or less. The algorithm is significantly simpler
than the shell sort, with only a small trade-off in efficiency. At the
same time, the insertion sort is over twice as fast as the bubble sort
and almost 40% faster than the selection sort."

http://linux.wku.edu/~lamonml/algor/sort/inse...

He gives sample C code for both, and the bubble sort has eight lines of
code, versus nine for insertion sort (excluding bare braces).

Perhaps what he should have said is:

"Bubble sort is a tiny bit simpler than insertion sort, and almost twice
as slow!"

--
Steven

Jeff Schwab

2/9/2008 9:29:00 PM

Steven D'Aprano wrote:
> On Fri, 08 Feb 2008 19:09:06 -0800, Jeff Schwab wrote:
>
>> 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.
>
> It depends on what you mean by "bubble sort". There are many different
> variations of bubble sort, that are sometimes described by names such as
> comb sort, cocktail sort, exchange sort, and sometimes merely referred to
> bubble sort. It's rather like any divide-and-conquer sorting algorithm
> being called quicksort.
>
> I'm as guilty of that as anyone else -- the example code I posted, raided
> from Wikibooks is very different from this bubble sort algorithm from
> PlanetMath:
>
> http://planetmath.org/encyclopedia/Bubbl...
>
> def bubblesort(L):
> done = False
> while not done:
> done = True
> for i in xrange(len(L)-1):
> if L[i+1] <= L[i]:
> L[i], L[i+1] = L[i+1], L[i]
> done = False
> return L
>
> This one runs significantly faster than the earlier one I posted.
>
> Another vital factor is, what language are you implementing the sort
> routine in? The conventional wisdom for low-level languages like assembly
> and C doesn't necessarily hold for high-level languages like Python.
> Comparisons are slow in Python and fast in C; in C a good algorithm will
> minimize the amount of moves, while in Python a good algorithm will
> minimize the number of comparisons.
>
> Finally, what hardware are you running on? There are interactions between
> hardware caches and pipes that can ruin the performance of an otherwise
> promising algorithm.
>
>
> But all those factors aside, I fear that your attempt to rehabilitate the
> reputation of bubble sort is misplaced. Here's another person who wants
> to defend bubble sort:
>
> "A fair number of algorithm purists (which means they've probably never
> written software for a living) claim that the bubble sort should never be
> used for any reason. Realistically, there isn't a noticeable performance
> difference between the various sorts for 100 items or less, and the
> simplicity of the bubble sort makes it attractive."
>
> http://linux.wku.edu/~lamonml/algor/sort/b...
>
> But then on the same person's page on insertion sort:
>
> "The insertion sort is a good middle-of-the-road choice for sorting lists
> of a few thousand items or less. The algorithm is significantly simpler
> than the shell sort, with only a small trade-off in efficiency. At the
> same time, the insertion sort is over twice as fast as the bubble sort
> and almost 40% faster than the selection sort."
>
> http://linux.wku.edu/~lamonml/algor/sort/inse...
>
> He gives sample C code for both, and the bubble sort has eight lines of
> code, versus nine for insertion sort (excluding bare braces).
>
> Perhaps what he should have said is:
>
> "Bubble sort is a tiny bit simpler than insertion sort, and almost twice
> as slow!"

So basically, you and I agree that the right sorting algorithm for the
job depends on the job. I have no particular interest in evangelizing
for bubble-sort; however, I hate to see an algorithm (or data structure,
or language, or programming style) taken out of the running before the
race even starts, just because it's out of fashion.

Jeff Schwab

2/9/2008 9:37:00 PM

Carl Banks wrote:
> On Feb 8, 10:09 pm, Jeff Schwab <j...@schwabcenter.com> wrote:
>> 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? You don't always have control over the
insertions/replacements, or where they happen. As a silly example,
assume you have a sorted list of children, by height. Maybe you check
your list once per school semester. The new sort order for any given
semester will likely be very close to the previous order; however, a few
swaps may be in order, according to the different speeds at which
children have grown.

> For a list of any decent size a few insertions using a bisection
> algorithm will take fewer comparisons than a single bubblesort pass.

Do you mean that if newly inserted data are kept separate from the
already-sorted list, then they can be merged into the list in O(log N) time?

Hrvoje Niksic

2/9/2008 10:08:00 PM

Steven D'Aprano <steve@REMOVE-THIS-cybersource.com.au> writes:

> It depends on what you mean by "bubble sort". There are many different
> variations of bubble sort, that are sometimes described by names such as
> comb sort, cocktail sort, exchange sort, and sometimes merely referred to
> bubble sort.

I've never seen anything better than bubble sort being called bubble
sort. Comb sort is definitely regarded as a different algorithm, and
cocktail sort is no better than bubble sort anyway.

> It's rather like any divide-and-conquer sorting algorithm being
> called quicksort.

Where have you seen this? I've never heard of non-quicksort
divide-and-conquer algorithms (such as mergesort) being referred to as
quicksort.

comp.lang.python

sort functions in python

t3chn0n3rd

Michael Spencer

Jeff Schwab

Steven D'Aprano

Jeff Schwab

Paddy

Carl Banks

Steven D'Aprano

Jeff Schwab

Jeff Schwab

Hrvoje Niksic

x Login to ForumsZone