Re: "Sorting" assignment

On Feb 6, 12:20 am, Julienne Walker <happyfro...@xxxxxxxxxxx> wrote:
On Feb 5, 10:56 am,spinoza1111<spinoza1...@xxxxxxxxx> wrote:

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.

Learning bubble sort can teach you a lot about algorithms. For

Cf. Thomas H Cormen et al. Introduction to Algorithms MIT 2001. Cormen
starts with insertion sort because it doesn't quite square the array
length, and his first full chapter on sorting describes heap and quick
sorting.

In my experience, the bubble sort is taught in those rather anti-
intellectual "practical, real-world" MIS computing classes which are a
fixture in Eastern Europe and elsewhere and which have the marvelous
result indeed of preparing students for a real range of jobs as a
opposed to programming, because their computer science content is
deliberately minimized lest the teacher be taken out into the yard and
shot (just kidding, sort of) but the ability to put up with the
nonsense is an indicator of ability to put up with further nonsense.

Cormen's approach doesn't work in these environments because secondary
schools, in my experience in the USA, perhaps elsewhere, have a bias
towards precalculus and analog computation and for this reason do a
poor job in teaching comfort with the sort of symbols and arguments
Cormen uses, which are those of finite mathematics. How to reason with
inequalities.

example, you can use bubble sort as a simple implementation for adding
step-based execution and performance analysis. It's a simple algorithm
for introducing asymptotic notation and time complexity. It's also an
immediately useful exercise that covers non-trivial loop and array
logic, modularization, and comparison based sorting. I'd hardly call
that "nothing of value".

Nothing of beauty. I'd say that the students have the right to start
with something of reasonable elegance and beauty which derives that
elegance and beauty from the fact that we developed this algorithm
before computers. The insertion sort can be illustrated and is
illustrated by Cormen using a poker hand.



Keep in mind that those learning bubble sort are likely to be very new
to programming, so while implementing the algorithm won't teach *you*
anything, it's very instructive to a less experienced programmer.

I am once again reminded of the title alone of Herbert Marcuse's study
of modern "civilization", One Dimensional Man. Marcuse is thought from
the outside to have mounted, circa 1970, some sort of Romantic
rebellion against "one dimensionality" and to have said something like
Hilary Clinton said in her Coke bottle glasses phase at Wellesley:
"But there are some things we feel, feelings that our prevailing,
acquisitive, and competitive corporate life, including tragically the
universities, is not the way of life for us. We're searching for more
immediate, ecstatic and penetrating mode of living."

But what Marcuse actually meant was that the one-dimensional mode
fails on its own terms. It fails when the one-dimensional and
unjustified schema of "less experienced" is imposed on the starter
programmer who may be closer to and more familiar with finite
mathematics.

Marcuse didn't think American culture failed to be more "immediate,
ecstatic and penetrating". He felt it was a rationalized
irrationality. Unlike his pal Adorno, he did not see that the
"immediate, ecstatic and penetrating" could be made a commodity and
become in fact a powerful tool of social control. However, he did see
a contradiction between the tentative way in which people talk about
other people in sets and classes (such as "less experienced
programmer") in such a way that the rule governing the set replaces
thought.


Naturally this is rather dependent on the teacher understanding these
lessons and guiding his or her students into learning them.

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.

I'm not sure I understand how you used "object oriented systems" and
"using generic parameters" to reach the conclusion of quicksort should
be taught because it uses a recursive call. I also disagree that

Because offline I've used an OO system with a single generic data type
parameter to develop a sort class for an arbitrary array, which
handles compare by Throwing an event which the user can handle to
return the comparision as -1 0 or 1.


quicksort should be the first sort taught to a student. You'd have to
wait until after recursion was introduced (quicksort is too
complicated to be an introduction to recursion), and even then it's an
extremely subtle algorithm that's better suited to students who have
had experience with simpler sorting algorithms.

In an ideal situation I (as the teacher) would give each student a
list of numbers and ask them to put it in order. That would give me an
idea of what sorting algorithm they think in and introduce them to the
simplest algorithm that implements that technique.

For example, I think in selections, so I would find selection sort to
be the easiest to learn as my first sort. I remember bubble sort
confused the hell out of me because I think in selection and not
exchange. I had similar difficulties with insertion sort, shell sort,

It confuses everyone and then becomes the "only" sorting algorithm.

and quicksort, but I picked up heap sort without any effort at all. So
in my experience, the best sort to teach first is the one that the
student is most likely to identify with.

I'd wager that the two algorithms born of that trick would be
selection sort and insertion sort, both of which are very simple and a
good stepping stone for moving into more efficient techniques.

-Jul

.