Re: sort on more than one key?
- From: spinoza1111@xxxxxxxxx
- Date: 9 Jun 2005 00:54:40 -0700
dave wrote:
> im using the quicksort algorithim. I can sort on one key no problem.But what
> is the correct way for
> sorting on more than one key, for example by last name then by first name. I
> know I can't sort on one and then run the sort on the other,
> at least I don't think so, I haven't tried but doesn't seem like it would
> work.
>
> thanks
Other posters have suggested using a stable sort such as the bubble
sort (yecchh) and aligning the major key (last name) considered as a
string into its max length and concatenating the minor key (first
name).
But by far the simplest algorithm is to use one sort (stable or
unstable) and in the compare function code the following for any pair
i,j of keypairs when they need to be compare to determine the sort
action.
if (majorKey[i] < majorKey[j]) ... perform actions for low compare ...
elseif (majorKey[i] > majorKey[j]) ... perform actions for high compare
....
elseif (minorKey[i] < minorKey[j]) ... low compare ...
elseif (minorKey[i] > minorKey(j]) ... high compare ...
else ... keys are equal ...
Consider that you have the human right to break down what seems a given
(comparing two keys) into an effective simulation of what the computer
does when it compares two numbers. If the computer can get away with
it, the computer is lazy: if at the beginning of a digitwise compare,
it sees that one compared number is order 10**3 and the other < 10**3,
or a smaller multiple of 10**3 the computer will call it a day and
report that the first number is greater than the second which it is.
Marcuse's theory of "surplus repression" can be applied to many
multipass algorithms in which the maintenance programmer discovers to
his horror that the programmer thought that it might be a good idea to
(1) sort exclusively on the major key and then (2) sort on the minor
key using (one hopes) a stable algorithm such as a nice "bubble" sort
(ai ya), writing let us say a massive intermediate file after pass (1)
pour encourager les autres.
Legacy programs are littered with lurid examples of sorting which are
indeed sordid and want what a Brit would call sorting out.
An occlusion of programmer psychology with the anthropomorphised, if
nonexistent, psychology of the computer causes the programmer to hope,
as if the computer were a prayer wheel chanting orisions to a cold
capitalist moon, that the extra cycles consumed might earn him
remission of sins, but, of course, they do not.
But, I digress.
Whenever you run up against a problem like this, think like the
computer, which is in fact a programme running in hardware and reflect
that you may always simulate what it does. For a set of keys k1, k2 ...
kn in major/minor order, consider it nothing more than a weird form of
number in a strange "missed radix" notation such that if ki>ki for a
given pair of these entities then the comparision is high, if ki<ki is
low, the comparision is low, and only otherwise must the compare
continue, to the last round and the last man, as it were.
In sorting, the one thing we consider obvious, the ability to compare
two entities, turns out on investigation to be far more interesting
than at first blush.
First of all, what might be "greater than" often is "less than" to the
end user with a perverted sense of humor, as in the case where we must
find the employee with the lowest performance rating, because the CEO
needs him for a delicate, James Bond-style mission (not for us to know
the mysteries of CEO psychology).
And as in this case, the key turns out to contain parts.
Early "sort utilities" had to expose the ability to code "exits"
typically to assembler routines in order to handle such cases. The
problem of "sorting" is one level of abstraction too high for it does
not specify the sort rule. Fortunately, all rules can be mapped onto
simple greater, less than or equal to in the final analysis.
Right? Right.
.
- References:
- sort on more than one key?
- From: dave
- sort on more than one key?
- Prev by Date: Re: proof of prior art
- Next by Date: Re: sort on more than one key?
- Previous by thread: Re: sort on more than one key?
- Next by thread: beginner's attempt at hash function
- Index(es):
Relevant Pages
|
