Re: "Sorting" assignment

On Feb 5, 8:01 pm, "Malcolm McLean" <regniz...@xxxxxxxxxxxxxx> wrote:
"Bartc" <b...@xxxxxxxxxx> wrote in message
I'd made a claim in this thread that bubble sort's speed might be
acceptable
for N in the hundreds. My test (on simple memory-based data and on my
machine) showed this could well be true.

Generally if the number of operations is trivial, you'll start to notice an
N^2 algorithm at N = 1000. It means 1 million operations, or say 100 million
machine instructions, which is a fraction of a second on a 3GHz machine.
You'll just notice the screen flicker as it updates.

What you won't notice is the way the module using bubble sort is an
invisible time sink. Sure, when you measure the time, it seems
trivial. But when the code exists in a multiprocessing system, it may
very well cause such irritating phenomena such as apparently frozen
progress reports in completely "unrelated" applications...that are
waiting for the Bubble Sort Kid's code to release the single CPU.

What's interesting is how excited people have gotten about truly de
minimis performance issues while claiming, in practice, that an N^2
algorithm such as tbe bubble sort should be given a free pass because
it seems, oh, so very simple. Sure, it's simple, so simple that in
implementing it you learn nothing of value.

"Above all, do no harm" would seem to indicate that you avoid the
bubble sort since in practice the number of elements could exceed
1000, and the bubble sort would affect overall performance without
ever being detected, as the culprit.

I've used order N^2 sorts, but I've used the interchange sort which is
closer to N^2/2. Not much of an improvement.

In modern, which is to say object oriented systems, sorts can be
provided once and for all for any array of any type by using generic
parameters. Which would seem to imply that sort should be taught
starting with quick sort, because in implementing it you do a
recursive call.

Guys like Ivica's teacher are thrown in secondary schools and
technical colleges to the wolves to teach useless techniques to
students who might never need to sort at all. Nobody, not the
administration and assuredly not the students, seem to have a handle
on what exactly should be taught. The teacher is given some
"materials" prepared by some former gnome and the students sense their
uselessness.


--
Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm

.

Relevant Pages

  • Re: sort functions in python
    ... bogo sort and bozo sort are worse, but bubble sort is still ... It's rather like any divide-and-conquer sorting algorithm being called quicksort. ... The conventional wisdom for low-level languages like assembly and C doesn't necessarily hold for high-level languages like Python. ...
    (comp.lang.python)
  • Re: sort functions in python
    ... insertions/replacements, or where they happen. ... The new sort order for any given ... In the case of bubble sort, I think it's a perfectly fine algorithm to ... of crystals that may grow at varying speeds, and that the sizes of the ...
    (comp.lang.python)
  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... Learning bubble sort can teach you a lot about algorithms. ... I'd say that the students have the right to start ...
    (comp.programming)
  • Re: problem in solving this.
    ... element is selected and placed at the end of the array. ... It looks like bubble sort to me. ... One swap per pass. ...
    (comp.lang.fortran)
  • Re: "Sorting" assignment
    ... realistic amounts of news, and it appears you ganged up on your ... difference between this and bubble sort. ... Students, I believe, don't find the bubble sort "simpler" except ...
    (comp.programming)