Re: "Sorting" assignment

On Feb 6, 5:15 pm, "Clive D. W. Feather" <cl...@on-the-
train.demon.co.uk> wrote:
In article
<99cf437b-e8d3-4d3c-92cc-909fb9d85...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,spinoza1111<spinoza1...@xxxxxxxxx> writes

Bubble sorting is how not
to sort.

Here is a C example of a simple program that sorts a list of random
numbers using the method of exchanging between two bins (partition
exchange) that I mentioned in my first post.

An algorithm which most people know as "quicksort", of course.

As I said, this algorithm grabs an arbitrary member and then compares
it to every other member, throwing each compared member into bin A or
bin B depending on whether it is greater than, or less than (or equal
to) the arbitrary member (called the pivot).

Actually, it doesn't. It grabs the member at the left end of the array
to be sorted. If the array is already sorted, this means that you end up
with an N^2 algorithm instead of an N log N one. About the only worse
choice you could have made is to use the one at the right end, since the
way you've coded it means that you'd also swap every single member of
the array with itself.

I don't have my old Knuth but I did snag an international edition of
Cormen (Not for Sale in the USA) at Commercial Press in Kowloon, and
yes, quick sort is fast (faster than heap sort) but not for ordered
and semi-ordered arrays.

Dijkstra based a fairly complex smoothsort on heapsort in the 1970s
which is n log n or N in all cases and transitions smoothly between
performance profiles: cf. http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a..PDF.

His paper exhibits his preference to be both subject and object, and
to present to himself the problem he would solve.

This way the solution is organically birthed by the problem statement.

Whereas in alienated labor the bubble sort is stillborn.

Much of what is called in corporations and technical borstals
"creative problem-solving" is creative, and solves problems, only by
accident, especially when it occurs in the borstal environment, now
generalized, in which "thou shalt not think too much, and you must
never make a mistake".
.

Relevant Pages

  • Re: "Sorting" assignment
    ... And many others prefer to call partition exchange because "quicksort" ... bin B depending on whether it is greater than, ... If the array is already sorted, this means that you end up ... attempt to sort them. ...
    (comp.programming)
  • Re: Integer math sort
    ... Suppose we have an array with three different values in it that looks ... which gives us computed indices of: ... which is sort of what we want but not really. ... each bin to get a histogram. ...
    (comp.programming)
  • Re: Integer math sort
    ... > Suppose we have an array with three different values in it that looks ... > which gives us computed indices of: ... > which is sort of what we want but not really. ... > each bin to get a histogram. ...
    (comp.programming)
  • Re: A Fast sorting algorithm for almost sorted data
    ... far my compressor has potential but is nowhere near ready. ... It does however make heavy use of sorting. ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ...
    (comp.compression)
  • A Fast sorting algorithm for almost sorted data
    ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ... public class RunSort implements Comparator ... public static void sort(Comparable a, int start,int end) ...
    (comp.compression)