peterk@cbmger.UUCP (Peter Kittel GERMANY) (05/02/91)
Anybody read the April Byte and the article about the new Combsort
algorithm? Recommended to everyone. Not only that it's a pure miracle
how one can achieve such a performance with such a little beastie
(you take bubble sort and *add two lines* and *change one other line*).
ABSOLUTELY INCREDIBLE.
But, for the best, if you look closely into one of the explanation
boxes, you find all this research (they obviously did an awful lot)
was done on an A2000.
I also thought at first, be careful it's the April issue, but I
immediately tested it and it seems to work, flawlessly and blindingly
fast. It looks as if it will replace my old loved heapsort that I used
the last years (I hate recursive algorithms like quicksort), because
Combsort beats Heapsort by a factor of 33 % on my machine (e.g. 12 s
against 16 s).
--
Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions...
Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterkrrmorris@uokmax.ecn.uoknor.edu (Rodney Raym Morrison) (05/03/91)
In article <1193@cbmger.UUCP> peterk@cbmger.UUCP (Peter Kittel GERMANY) writes: >Anybody read the April Byte and the article about the new Combsort >algorithm? Recommended to everyone. Not only that it's a pure miracle >how one can achieve such a performance with such a little beastie >(you take bubble sort and *add two lines* and *change one other line*). >ABSOLUTELY INCREDIBLE. >But, for the best, if you look closely into one of the explanation >boxes, you find all this research (they obviously did an awful lot) >was done on an A2000. > >I also thought at first, be careful it's the April issue, but I >immediately tested it and it seems to work, flawlessly and blindingly >fast. It looks as if it will replace my old loved heapsort that I used >the last years (I hate recursive algorithms like quicksort), because >Combsort beats Heapsort by a factor of 33 % on my machine (e.g. 12 s >against 16 s). > >-- >Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Could you post your combsort code or email it to me? rrmorris@uokmax.ecn.uoknor.edu
ccplumb@rose.waterloo.edu (Colin Plumb) (05/04/91)
I saw it briefly and was thrilled that BYTE had finally discovered shellsort. If it beats heapsort, though, I may be wrong. How does it work? -- -Colin
peterk@cbmger.UUCP (Peter Kittel GERMANY) (05/06/91)
In article <1991May3.201243.7959@watdragon.waterloo.edu> ccplumb@rose.waterloo.edu (Colin Plumb) writes: >I saw it briefly and was thrilled that BYTE had finally discovered shellsort. >If it beats heapsort, though, I may be wrong. How does it work? In the article, they explicitly mention shellsort. They say that their combsort may look very similar, but is quite a different thing then. -- Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (05/06/91)
ccplumb@rose.waterloo.edu (Colin Plumb) writes: > I saw it briefly and was thrilled that BYTE had finally discovered > shellsort. If it beats heapsort, though, I may be wrong. How does it > work? Much like shell-sort, but instead of decreasing the span by a factor of 1.7 or so per loop, and then repeating each loop until no swaps are seen, the span is decreased by only 1.3 per loop, but each loop runs just once until the span one loop, which is run until no swaps occur. There seems also to be some special casing that a span of 9 or 10 is replaced by a span of 11 for reasons worth reading the article to puzzle out. I did the same about 1967, as I'm sure did thousands of others; the authors' biggest contribution is to run thorough tests to pick the "ideal" span divisor from loop to loop, and to detail performance. While it does (barely) beat heapsort, it takes almost twice as long as quicksort, so it is still not a choice you'd make except in a small sort, quick hack application. As a recent net posting showing quicksort in ML proved, there is nothing inherently complex about quicksort, our notation for programming just makes it look complex with a lanugage as weak as C. In such a procedural language, though, the comb-sort _looks_ much simpler, and is surely simpler to write, than either quicksort or heapsort. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
peterk@cbmger.UUCP (Peter Kittel GERMANY) (05/07/91)
In article <1991May3.165222.31097@uokmax.ecn.uoknor.edu> rrmorris@uokmax.ecn.uoknor.edu (Rodney Raym Morrison) writes: >In article <1193@cbmger.UUCP> peterk@cbmger.UUCP (Peter Kittel GERMANY) writes: >>Anybody read the April Byte and the article about the new Combsort >>algorithm? Recommended to everyone. >>But, for the best, if you look closely into one of the explanation >>boxes, you find all this research (they obviously did an awful lot) >>was done on an A2000. >> ^^^^^^^^^^^^^^^^ >>I also thought at first, be careful it's the April issue, but I >>immediately tested it and it seems to work, flawlessly and blindingly >>fast. It looks as if it will replace my old loved heapsort that I used >>the last years (I hate recursive algorithms like quicksort), because >>Combsort beats Heapsort by a factor of 33 % on my machine (e.g. 12 s >>against 16 s). > >Could you post your combsort code or email it to me? I got some more similar requests, so here we go. Naturally, we speak AmigaBASIC (-: for the not BASIC literates there is also a C version in the Byte article :-) : rem Combsort, by Richard Box and Stephen Lacey, Byte 4/91, p.315 rem Sort Array a(1) to a(size), start index 0 no problem (change FOR) gap=size flag=-1:rem this is a boolean flag while flag or gap<>1 gap=int(gap/1.3):if gap<1 then gap=1 if gap=9 or gap=10 then gap=11 flag=0 for i=1 to size-gap j=i+gap if a(i)>a(j) then ah=a(i):a(i)=a(j):a(j)=ah flag=-1 end if next wend Well, originally they use a "DO ... UNTIL flag=0 and gap" in TrueBasic, which is not available in AmigaBASIC. You may well do it that way in assembler. (I hope my WHILE does indeed exactly the same.) The only place where you had to change something to work on an array starting with index 0 is the FOR loop. For the assembler gurus: The crucial part is that divisor 1.3. If you are going fixed point in assembler, you need not use it to 12 digits precision, values between 1.28 and 1.31 are nearly as good. So you may choose some value that shows some easy-to-divide bit pattern. (They show a diagram made up of 20,000 test arrays and different gap values, showing the sort time depending on gap. The curve shows a definite minimum at 1.3, leading into chaos for bigger values, and steadily rising for lower values.) The special treatment of gap=9 or 10 is already a refinement of 2nd stage, not needed vitally, but reportedly optimizing the performance and really easy to implement. Have fun and tell me about your results! -- Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
peter@cbmvax.commodore.com (Peter Cherna) (05/07/91)
In article <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >While it does (barely) beat heapsort, it takes almost twice as long >as quicksort, so it is still not a choice you'd make except in a small >sort, quick hack application. As a recent net posting showing >quicksort in ML proved, there is nothing inherently complex about >quicksort, our notation for programming just makes it look complex >with a lanugage as weak as C. Quicksort is even easier to "write" when you find it has already been implemented in a link-library. SAS/C comes with a quicksort that has several interfaces (one for integers, one for strings, etc.) Other compilers may have the same. (It's worth reading through the section of the manual on the link libraries -- there are a really rich set of functions available.) >Kent, the man from xanth. Peter -- Peter Cherna, Operating Systems Development Group, Commodore-Amiga, Inc. {uunet|rutgers}!cbmvax!peter peter@cbmvax.commodore.com My opinions do not necessarily represent the opinions of my employer. "If all you have is a hammer, everything looks like a nail."
231b3678@fergvax.unl.edu (Phil Dietz) (05/08/91)
In <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >While it does (barely) beat heapsort, it takes almost twice as long >as quicksort, so it is still not a choice you'd make except in a small >sort, quick hack application. As a recent net posting showing >quicksort in ML proved, there is nothing inherently complex about >quicksort, our notation for programming just makes it look complex >with a lanugage as weak as C. I was VERY amazed at the comb-sorts results. I ran the test on my system, and you know what, comb-sort beat qsort by a heinous time! I sorted a list of ints (100000 of them). I used the comb-sort routine directly from the article, and I used qsort routine that comes with Lattice. sorting the same list of 100000 elements: qsort 165.3 secs comb 53.2 secs This either shows that the comb-sort is FAST, or the Lattice Qsort is SLOW! Yes 3 times faster! Here is the source code to compile on your system: Keep in mind that I just threw this together....(wnat some spaghetti ? :-) Compile lc -Lm -O comb.c #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> void main(int argc, char **argv) { void combsort(int *list,int size); int sortfunct(int *a, int *b); int i,*list,size; unsigned int clock[2],clock2[2]; if (argc<3) { printf("combsort [ 1 | 2 ] [# of elements]\n 1 = comb\n 2 = qsort\n\n"); exit(1); } size=atoi(argv[2]); if (size<10) exit(1); list=(int *)calloc(size,sizeof(int)); if (!list) { printf(" Ran out of memory!\n"); exit(1); } for (i=0;i<size;i++) list[i]=(rand() % size); /* Get random list */ for (i=0;i<10;i++) printf("%d: %d\n",i,list[i]); /* Print some of them */ timer(clock); if (atoi(argv[1])==1) { printf("Comb Sorting:\n"); combsort(list,size); } else { printf("Q-Sorting\n"); qsort(list,size,sizeof(int),sortfunct); } timer(clock2); printf("\nSorted:\n"); for (i=0;i<10;i++) printf("%d: %d\n",i,list[i]); printf("Time 1: %d.%d\n",clock[0],clock[1]); printf("Time 2: %d.%d\n",clock2[0],clock2[1]); if (clock[1]>clock2[1]) printf("Total time: %d.%d secs\n",(clock2[0]-clock[0]),(clock[1]-clock2[1])); else printf("Total time: %d.%d secs\n",(clock2[0]-clock[0]),(clock2[1]-clock[1])); } void combsort(int *list,int size) { int switches, hold, i, j, top, gap; gap=size; do { gap=(int)((float)gap/1.3); switch(gap) { case 0: gap=1; break; case 9: case 10: break; default: break; } switches=0; top=size - gap; for(i=0;i<top;++i) { j=i+gap; if (list[i] > list[j]) { hold=list[i]; list[i]=list[j]; list[j]=hold; ++switches; } } } while (switches || (gap>1)); } int sortfunct(int *a, int *b) { if (*a>*b) return 1; if (*a<*b) return -1; return 0; } --- I don't like to flame! Phil Dietz You know what? 231b3678@fergvax.unl.edu Newton and Leibniz suck big time! Univ. of Nebraska
mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) (05/08/91)
In article <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes:
While it does (barely) beat heapsort, it takes almost twice as long
as quicksort, so it is still not a choice you'd make except in a small
sort, quick hack application.
Actually, for that kind of application, I use sort(). What's the point
of having libraries of tools if you don't use them for the quick
hacks. In fact, even for non-quick hacks, it's probably worthwhile
using sort(), and replacing it if it proves to be unsuitable for some
reason.
<mike
--
I know the world is flat. Mike Meyer
Don't try tell me that it's round. mwm@pa.dec.com
I know the world stands still. decwrl!mwm
Don't try to make it turn around.peterk@cbmger.UUCP (Peter Kittel GERMANY) (05/08/91)
In article <231b3678.673637576@fergvax> 231b3678@fergvax.unl.edu (Phil Dietz) writes: > >void combsort(int *list,int size) > { > ... > switch(gap) > { > case 0: gap=1; break; > case 9: case 10: break; ^^^^^ I miss something here: gap=11; ??? > default: break; > } > switches=0; > .... > if (list[i] > list[j]) > { > hold=list[i]; > list[i]=list[j]; > list[j]=hold; > ++switches; ^^ Why do they do this? Why not just set the flag? Or is a "++switches;" faster than a "switches=1;" (done by MOVEQ in assembler)? -- Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
dac@prolix.pub.uu.oz.au (Andrew Clayton) (05/08/91)
In article <MWM.91May7111453@raven.pa.dec.com>, Mike (My Watch Has Windows writes: > In article <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: > While it does (barely) beat heapsort, it takes almost twice as long > as quicksort, so it is still not a choice you'd make except in a small > sort, quick hack application. > > Actually, for that kind of application, I use sort(). What's the point > of having libraries of tools if you don't use them for the quick > hacks. In fact, even for non-quick hacks, it's probably worthwhile > using sort(), and replacing it if it proves to be unsuitable for some > reason. If you want a sad laugh; Mickeysoft C V6.00 for the MSDOS platform has a sort() library function, all very well and good. Microsoft Windows (V3) has listboxes that can be flagged as 'sorted'. Fine. Unfortunately, Windows doesn't use the sort() library - it has its OWN completely incompatible collating sequence that places all punctuation and special symbols BEFORE letters, and all the numerals AFTER letters. It's truly spasticated, and a real bitch to work with. Grr. > I know the world is flat. Mike Meyer Dac --
mjl@alison.at (Martin J. Laubach) (05/09/91)
| In article <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: | While it does (barely) beat heapsort, it takes almost twice as long | as quicksort Pardon me -- I don't want to start a "my sort is better than your sort" thread, I just want to find out whether the stuff we learnt is correct or not... Following my docs, heapsort always does O(N ld N), while quicksort is N ld N (best), N^2/2 (worst case), and 1.4 N ld N (average). Doesn't this mean that heap and quick are about the same, but the possibility of an anomaly in quicksort? mjl
mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) (05/09/91)
In article <231b3678.673637576@fergvax> 231b3678@fergvax.unl.edu (Phil Dietz) writes: In <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >While it does (barely) beat heapsort, it takes almost twice as long >as quicksort, so it is still not a choice you'd make except in a small >sort, quick hack application. I was VERY amazed at the comb-sorts results. I ran the test on my system, and you know what, comb-sort beat qsort by a heinous time! I sorted a list of ints (100000 of them). I used the comb-sort routine directly from the article, and I used qsort routine that comes with Lattice. sorting the same list of 100000 elements: qsort 165.3 secs comb 53.2 secs This either shows that the comb-sort is FAST, or the Lattice Qsort is SLOW! No, it shows what happens when you compare a general sort utility to one tailored for the problem at hand. Your comb-sort got to use a direct comparisons and assignments instead of a function calls. That makes each comparison and exchange an order of magnitude (or more) more expensive for SAS qsort than for your coomb-sort. A closer-to-fair comparison would be to write your own quicksort for sorting a fixed-size array of known object types. I cheated, and tweaked your comb-sort to call sortfunct for the comparison, and memcpy for the assignments, whicih should have roughly the same effect. I got: comb-sort of 100000 elements: 42.46 seconds qsort of 100000 elements: 27.12 seconds I.e. - the quicksort is roughly twice as fast for this case. Note: what I did - or even what I suggested doing - doesn't constitute a serious study of the problem. It just points out the flaws in what was presented earlier. In reality, I'll continue using qsort(), even though I can get faster results by handcoded routines. When a profiled run of the code shows that the serious delays are caused by the qsort, I'll change it to something faster, and chosen for the problem at hand. Meanwhile, I'm waiting to see what BSD is going to do with Bernsten's combinatorial sort, which sorts things in order(total_keysize). And there's a thing called "fusion sort" that might be the same thing in another guise.... <mike -- Take a magic carpet to the olden days Mike Meyer To a mythical land where everybody lays mwm@pa.dec.com Around in the clouds in a happy daze decwrl!mwm In Kizmiaz ... Kizmiaz
Charlie_Gibbs@mindlink.bc.ca (Charlie Gibbs) (05/09/91)
In article <191c1d82.ARN1dba@prolix.pub.uu.oz.au> dac@prolix.pub.uu.oz.au (Andrew Clayton) writes: >Unfortunately, Windows doesn't use the sort() library - it has >its OWN completely incompatible collating sequence that places >all punctuation and special symbols BEFORE letters, and all the >numerals AFTER letters. It's truly spasticated, and a real bitch >to work with. Grr. My God! That's just like EBCDIC! IBM is everywhere! Charlie_Gibbs@mindlink.bc.ca "I'm cursed with hair from HELL!" -- Night Court
limonce@pilot.njin.net (Tom Limoncelli +1 201 408 5389) (05/09/91)
In article <MWM.91May8182512@raven.pa.dec.com> mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) writes: > A closer-to-fair comparison would be to write your own quicksort for > sorting a fixed-size array of known object types. I cheated, and >[...] > comb-sort of 100000 elements: 42.46 seconds > qsort of 100000 elements: 27.12 seconds If you want to be even more closer-to-fair you wouldn't give results for only sorting one amount of numbers. You should really show a graph of how they work on 1000, 2000, 3000, 5000, 10000, 15000... (note the logorithmic increase) elements. Of course, if you want to be the most accurate (by computer theory standards) you wouldn't even run the program! You'd just figure the O() of the function. > In reality, I'll continue using qsort(), even though I can get faster > results by handcoded routines. When a profiled run of the code shows > that the serious delays are caused by the qsort, I'll change it to > something faster, and chosen for the problem at hand. I now do just about all my programming like that. I don't think I've written a new line of code in years. :-) -- Tom Limoncelli tlimonce@drew.edu tlimonce@drew.bitnet 201-408-5389 Three witches making a potion. One asks, "A Liza Minnelli record, light beer, poppers, Frye boots; what's this spell for anyway?"
bombadil@diku.dk (Kristian Nielsen) (05/09/91)
231b3678@fergvax.unl.edu (Phil Dietz) writes: >I was VERY amazed at the comb-sorts results. I ran the test on my system, and >you know what, comb-sort beat qsort by a heinous time! I sorted >a list of ints (100000 of them). I used the comb-sort routine directly >from the article, and I used qsort routine that comes with Lattice. > > sorting the same list of 100000 elements: qsort 165.3 secs > comb 53.2 secs > >This either shows that the comb-sort is FAST, or the Lattice Qsort is SLOW! >Yes 3 times faster! Here is the source code to compile on your system: >Keep in mind that I just threw this together....(wnat some spaghetti ? :-) > >Compile lc -Lm -O comb.c > if (atoi(argv[1])==1) > { > printf("Comb Sorting:\n"); > combsort(list,size); > } > else > { > printf("Q-Sorting\n"); > qsort(list,size,sizeof(int),sortfunct); > } > >int sortfunct(int *a, int *b) > { > if (*a>*b) return 1; > if (*a<*b) return -1; > return 0; > } Though this is not a claim of qsort being better that compsort (I really wouldn't know), it should be remarked that the above isn't really a fair way to compare the two algorithms. The reason is that the qsort function used is much more general than the compsort, being able to sort elements of any size and ordering. This introduces rather large overheads in the inner loops, since qsort has to make a function call for each compare, and perhaps also for each element swap (memcpy?). Combsort does all of this inline, optimised for a fixed size. How about rewriting compsort to be as general as qsort (caller-specified size and ordering-function), and posting the results? - Kristian.
hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) (05/10/91)
> In article <MWM.91May8182512@raven.pa.dec.com> mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) writes: > > > A closer-to-fair comparison would be to write your own quicksort for > > sorting a fixed-size array of known object types. I cheated, and > >[...] > > comb-sort of 100000 elements: 42.46 seconds > > qsort of 100000 elements: 27.12 seconds > > If you want to be even more closer-to-fair you wouldn't give results > for only sorting one amount of numbers. You should really show a > graph of how they work on 1000, 2000, 3000, 5000, 10000, 15000... (note > the logorithmic increase) elements. > > Of course, if you want to be the most accurate (by computer theory > standards) you wouldn't even run the program! You'd just figure the > O() of the function. ^^^^^^ Perhaps you know, that there is a computer-theory-theorey proof, that no comparision-based sorting algorithm can run faster than O(n log n) which is a lower bound for sorting. Which bucket-sort you can even achieve O(n)! For details on this subject see U.Manber : 'Introduction to Algorithms' (Addison-Wesley ISBN 0-201-12037-2) Chapter 6.4.6 and D.E.Knuth : 'The Art of computer programming - sorting and searching' (Addison-Wesley ISBN unknown) In the articles you will see, that Quicksort ist the fastest comparision- based sorting algorithm on the average, but it may take O(n*n) in the worst case. Heapsort on the other side is guaranteed to sort in O(n log n), but in the average case it is slower than Quicksort. Quicksort's running time depends on the input an on it's implementation. Hope that helps ... -Heiko -- Heiko W.Rupp, Gerwigstr.5, D-7500 Karlsruhe 1 | hwr@pilhuhn.ka.sub.org Tel: +49 7021 693642 (voice only) | uk85@dkauni2.bitnet All opinions expressed are my own, but sometimes I don't know what I say Gruesse -Heiko -- Heiko W.Rupp, Gerwigstr.5, D-7500 Karlsruhe 1 | hwr@pilhuhn.ka.sub.org Tel: +49 7021 693642 (voice only) | uk85@dkauni2.bitnet All opinions expressed are my own, but sometimes I don't know what I say
allbery@NCoast.ORG (Brandon S. Allbery KB8JRR/AA) (05/10/91)
As quoted from <231b3678.673637576@fergvax> by 231b3678@fergvax.unl.edu (Phil Dietz): +--------------- | you know what, comb-sort beat qsort by a heinous time! I sorted | a list of ints (100000 of them). I used the comb-sort routine directly | from the article, and I used qsort routine that comes with Lattice. | | sorting the same list of 100000 elements: qsort 165.3 secs | comb 53.2 secs | | This either shows that the comb-sort is FAST, or the Lattice Qsort is SLOW! +--------------- If Lattice's qsort() is anything like the one in the Unix standard C library, it's a pretty good proof that any algorithm can be implemented to run as slow as you like. :-) :-( ++Brandon -- Me: Brandon S. Allbery Ham: KB8JRR/AA 10m,6m,2m,220,440,1.2 Internet: allbery@NCoast.ORG (restricted HF at present) Delphi: ALLBERY AMPR: kb8jrr.AmPR.ORG [44.70.4.88] uunet!usenet.ins.cwru.edu!ncoast!allbery KB8JRR @ WA8BXN.OH
pds@quintus.UUCP (Peter Schachte) (05/11/91)
In article <mjl.8698@alison.at> mjl@alison.at writes: > Following my docs, heapsort always does O(N ld N), while quicksort >is N ld N (best), N^2/2 (worst case), and 1.4 N ld N (average). There are lots of N log N sorts, so the constant factors start getting important in choosing. Also note that you need to consider both the number of comparisons as well as the number of exchanges. In fact, if you sort an array of pointers to records, exchanges are pretty cheap. And if your keys are strings rather than integers, comparisons are much more expensive. It's often more important to minimize the numer of comparisons rather than the number of exchanges. -- -Peter Schachte pds@quintus.com ...!{uunet,sun}!quintus!pds
krsear02@ulkyvx.bitnet (Kendall 'Opusii' Sears) (05/13/91)
[oh for a real reader!] >I saw it briefly and was thrilled that BYTE had finally discovered shellsort. >If it beats heapsort, though, I may be wrong. How does it work? > > -Colin This is exactly what I thought when I saw the article. It was sad though, I remember a time when BYTE was one of the first mags to publish new algs but now they seem to be re-publishing other peoples' articles; the 'shell-sort' was in a Compute! or Compute!'s Gazette (I don't remember which) way back when... Geez am I *THAT* old? Kendall. -- Kendall "Opusii" Sears KRSEAR02@ULKYVX.bitnet Programmer /// Child Development Unit /// Amiga Department of Pediatrics \\\/// Currently running AmigaOS 2.0 University of Louisville \XX/ And Supporting Unix Sys V Rev 4. --------------------------------------------------------------------------- "Numbness is bliss... I can't feel a thing." -me.
dvljrt@cs.umu.se (Joakim Rosqvist) (05/13/91)
In article <191d6f59.ARN12eb@pilhuhn.ka.sub.org> hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) writes: >> In article <MWM.91May8182512@raven.pa.dec.com> mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) writes: >> >> > A closer-to-fair comparison would be to write your own quicksort for >> > sorting a fixed-size array of known object types. I cheated, and >> >[...] >> > comb-sort of 100000 elements: 42.46 seconds >> > qsort of 100000 elements: 27.12 seconds >> >In the articles you will see, that Quicksort ist the fastest comparision- >based sorting algorithm on the average, but it may take O(n*n) in the Has anybody timed Quicksort in assembler? I just made a comb-sort that will sort 100000 integers in 18.5 sec /$DR.HEX$
peterk@cbmger.UUCP (Peter Kittel GERMANY) (05/14/91)
In article <1991May13.073134.330@ulkyvx.bitnet> krsear02@ulkyvx.bitnet (Kendall 'Opusii' Sears) writes: >[oh for a real reader!] > >>I saw it briefly and was thrilled that BYTE had finally discovered shellsort. >>If it beats heapsort, though, I may be wrong. How does it work? >> >> -Colin >This is exactly what I thought when I saw the article. It was sad though, >I remember a time when BYTE was one of the first mags to publish new algs >but now they seem to be re-publishing other peoples' articles; the >'shell-sort' was in a Compute! or Compute!'s Gazette (I don't remember which) >way back when... Geez am I *THAT* old? But if you read the article thoroughly, you'll find that the authors indeed know sell-sort and compare their algorithm to it, finding out that the two are more different than from first sight. Combsort appears to be much faster than shell-sort. -- Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
ttobler@unislc.uucp (Trent Tobler) (05/16/91)
From article <191d6f59.ARN12eb@pilhuhn.ka.sub.org>, by hwr@pilhuhn.ka.sub.org (Heiko W.Rupp): > >> Of course, if you want to be the most accurate (by computer theory >> standards) you wouldn't even run the program! You'd just figure the >> O() of the function. > ^^^^^^ > Perhaps you know, that there is a computer-theory-theorey proof, that no > comparision-based sorting algorithm can run faster than O(n log n) which > is a lower bound for sorting. That is correct. He was saying to calculate the time function of the comb sort compared to the quick sort. I believe the article stated that the comb-sort algorithem appeared to be an O(n*ln n) sort. In other words, as more elements are sorted, the ratio of time(quicksort)/time(combsort) remains constant. > Which bucket-sort you can even achieve O(n)! ^^^ is this suppost to be 'With'? And anyway, who can afford the memory with a bucket sort on any generic data? (Isn't the bucket sort the one where for each element, an integer is calculated which has the property such that A<B for items A and B, f(A) < f(B) holds; and then to do the sort, you simply increment the count of C[f(X)], and then reconstructing the list based on C?) > > In the articles you will see, that Quicksort ist the fastest comparision- > based sorting algorithm on the average, but it may take O(n*n) in the > worst case. No, there are sorts which are faster. > Heapsort on the other side is guaranteed to sort in O(n log n), > but in the average case it is slower than Quicksort. Quicksort's running > time depends on the input an on it's implementation. > Quicksort also uses additional memory. As N gets larger, the amount of memory above that contained in the array to sort grows by ln(N). Heapsort and combsort are both iteritive sorts, which means they use a constant amount of memory for any N. I have an algorithem based on the merge sort that runs about the same as quick sort on random lists, and runs even faster on near-sorted lists. It's problem is that its memory requirements grow by N/2. Of the sorts that I have tested, Quicksort tends to minimize the number of moves on elements, but requires. Combsort did about twice the number of moves as quicksort, and about the same number of compares. The m-sort I tested tended to minimize the number of comparisions, about 50% of that quicksort required, but required 100% more moves. Here is a table I constructed showing various sort statistics: Random Sorted Backward-Sorted 10 100 1000 10 100 1000 10 100 1000 bubble-sort compares 45 4872 499455 9 99 999 45 4950 499500 moves 78 7413 722256 0 0 0 135 14850 1498446 comb-sort compares 32 1096 19706 32 1096 19706 32 1096 19706 moves 30 801 12612 0 0 0 21 348 4596 heap-sort compares 39 1030 16878 41 1081 17570 35 944 15966 moves 62 1041 13920 74 1134 14677 53 910 12314 m-sort compares 29 603 9403 15 316 4932 28 455 6047 moves 34 777 12942 0 0 0 49 988 14887 quick-sort compares 35 861 14878 45 4950 499500 50 5000 500000 moves 24 365 5066 18 198 1998 23 248 2498 shell-sort compares 32 704 13985 15 342 5457 21 500 8541 moves 52 1089 19883 30 684 10914 43 914 14825 The algorithems used were bubble: compare neighbors, swap if out of order. comb: described in Byte, April 1991 heap: vanilla heap sort m-sort: 1) divide list in half. 2) If size of either half > 2, recursively sort it. 3) merge sort each half (they are each in order because of (2)) quick: vanilla quicksort shell-sort: 3n+1 shell sort --- Trent Tobler - ttobler@csulx.weber.edu
mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) (05/18/91)
In article <1991May15.220144.27507@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes: > Which bucket-sort you can even achieve O(n)! ^^^ is this suppost to be 'With'? And anyway, who can afford the memory with a bucket sort on any generic data? (Isn't the bucket sort the one where for each element, an integer is calculated which has the property such that A<B for items A and B, f(A) < f(B) holds; and then to do the sort, you simply increment the count of C[f(X)], and then reconstructing the list based on C?) Well, that's one form of bucket sort. For sorting generic data, it's probably better to do a multi-pass bucket sort, where you sort on one byte of the key on each pass. Net result is a sort that is O(keysize), for the total size of the keys (it can't be expressed cleanly in terms of the number of keys). With equal-size objects, this can be done in place. <mike -- Don't tell me how to live my life Mike Meyer Don't tell me what to do mwm@pa.dec.com Repression is always brought about decwrl!mwm by people with politics and attitudes like you.
andand@cia.docs.uu.se (Anders Andersson) (05/31/91)
In <1991May15.220144.27507@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes: >From article <191d6f59.ARN12eb@pilhuhn.ka.sub.org>, by hwr@pilhuhn.ka.sub.org (Heiko W.Rupp): >> >>> Of course, if you want to be the most accurate (by computer theory >>> standards) you wouldn't even run the program! You'd just figure the >>> O() of the function. >> ^^^^^^ >> Perhaps you know, that there is a computer-theory-theorey proof, that no >> comparision-based sorting algorithm can run faster than O(n log n) which >> is a lower bound for sorting. >That is correct. He was saying to calculate the time function of the comb >sort compared to the quick sort. I believe the article stated that >the comb-sort algorithem appeared to be an O(n*ln n) sort. In other >words, as more elements are sorted, the ratio of time(quicksort)/time(combsort) >remains constant. Yes, I made a quick calculation that suggested that quicksort is 1.9 times faster. I tried to tell the world (or rather this newsgroup) but my message bounced. >> Which bucket-sort you can even achieve O(n)! > ^^^ is this suppost to be 'With'? >And anyway, who can afford the memory with a bucket sort on any generic data? >(Isn't the bucket sort the one where for each element, an integer is calculated > which has the property such that A<B for items A and B, f(A) < f(B) holds; and > then to do the sort, you simply increment the count of C[f(X)], and then > reconstructing the list based on C?) I'm not sure what bucket sort is, but radix sort is O(n) and it 'only' requires twice the memory (i.e. it needs a extra copy of the data). In a general application, you only sort pointers to data objects, so this isn't too bad. >> >> In the articles you will see, that Quicksort ist the fastest comparision- >> based sorting algorithm on the average, but it may take O(n*n) in the >> worst case. >No, there are sorts which are faster. It all depends on what data you are sorting. Quicksort usually beets other sorts hands down in tests, mostly because it has a extremly short inner loop. This is a great advantage when sorting an array of integers or something, but not equally important in practice when each compare is associated with some overhead. [stuff deleted] >Of the sorts that I have tested, Quicksort tends to minimize the number of >moves on elements, but requires. Combsort did about twice the number of >moves as quicksort, and about the same number of compares. The m-sort I ^^^^^^^^^^^^^^^^^^^^^^^ >tested tended to minimize the number of comparisions, about 50% of that >quicksort required, but required 100% more moves. That's strange. Acording to my sources on quicksort and my own calculations of combsort, combsort should require 1.9 times as many compares. I might have missed something, but I can't imagine what. I should be able to count my way through nested loops... [stuff deleted] -Anders Andersson (andand@cia.docs.uu.se)
hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) (06/04/91)
In article <andand.675707397@cia.docs.uu.se>, Anders Andersson writes: > In <1991May15.220144.27507@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes: > > >From article <191d6f59.ARN12eb@pilhuhn.ka.sub.org>, by hwr@pilhuhn.ka.sub.org (Heiko W.Rupp): > > [..] > >> Which bucket-sort you can even achieve O(n)! > > ^^^ is this suppost to be 'With'? Yup ! > > > I'm not sure what bucket sort is, but radix sort is O(n) and it 'only' requires > twice the memory (i.e. it needs a extra copy of the data). In a general application, > you only sort pointers to data objects, so this isn't too bad. Bucketsort: Imagine that You have 50 States. Bucket sort means now sorting the letters according to the name of the State in one of 50 Boxes (or Buckets) labeled with the name of the State. Going once through the data costs O(n); adding an element to the head of the list costs O(1) -> You get linear (O(n)) running time. Gruesse -Heiko -- Heiko W.Rupp, Gerwigstr.5, D-7500 Karlsruhe 1 | hwr@pilhuhn.ka.sub.org Tel: +49 7021 693642 (voice only) | uk85@dkauni2.bitnet They say that killing a shopkeeper brings bad luck.
ttobler@unislc.uucp (Trent Tobler) (06/04/91)
From article <andand.675707397@cia.docs.uu.se>, by andand@cia.docs.uu.se (Anders Andersson): >>No, there are sorts which are faster. > > It all depends on what data you are sorting. Quicksort usually beets > other sorts hands down in tests, mostly because it has a extremly short inner > loop. This is a great advantage when sorting an array of integers or something, > but not equally important in practice when each compare is associated with some > overhead. There are actually sorts that beat quicksort on all data of a certain size of greater (they are quite complex, can't remember there names right now.) >>Of the sorts that I have tested, Quicksort tends to minimize the number of >>moves on elements, but requires. Combsort did about twice the number of >>moves as quicksort, and about the same number of compares. The m-sort I > ^^^^^^^^^^^^^^^^^^^^^^^ >>tested tended to minimize the number of comparisions, about 50% of that >>quicksort required, but required 100% more moves. > > That's strange. Acording to my sources on quicksort and my own calculations > of combsort, combsort should require 1.9 times as many compares. I might have Well, combsort requires about twice the moves, and about the same number of compares, so if q-sort requires 15000 compares, and 5000 moves, then that is 20000 operations. The corresponding comb-sort would require 20000 compares, and would require 13000 moves, so that would mean 33000 operations; comb-sort is slower by about 1.65 times if compares and moves take about the same amount of time. Again, the main advantage (as I see it) of the comb-sort is that it's memory requirements are constant for ANY array. (true, quick-sort only requires ln(N)+C units of additional memory, which is not a lot) > -Anders Andersson (andand@cia.docs.uu.se) -- Trent Tobler - ttobler@csulx.weber.edu
tdsmith@oasys.dt.navy.mil (Timothy Smith) (06/07/91)
In article <193e8efd.ARN1453@pilhuhn.ka.sub.org> hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) writes: >Imagine that You have 50 States. Bucket sort means now sorting the letters >according to the name of the State in one of 50 Boxes (or Buckets) labeled >with the name of the State. Going once through the data costs O(n); adding >an element to the head of the list costs O(1) -> You get linear (O(n)) running >time. What? Start with an unsorted list of n objects (or pointers to objects, same thing...) Is there a sort algorithm which is o(n)? If so, use it to sort (23 41 55 12 11 9 10) with only 7 moves. I'm skeptical! Tim
tdsmith@oasys.dt.navy.mil (Timothy Smith) (06/07/91)
>it to sort (23 41 55 12 11 9 10) with only 7 moves. I'm skeptical! er, with only 7 "reads". Sorry about the second posting. >Tim
231b3678@fergvax.unl.edu (Phil Dietz) (06/07/91)
In <8236@oasys.dt.navy.mil> tdsmith@oasys.dt.navy.mil (Timothy Smith) writes: >>it to sort (23 41 55 12 11 9 10) with only 7 moves. I'm skeptical! >er, with only 7 "reads". Sorry about the second posting. >>Tim Simply use a hash function of f(x) = x The only way a bucket sort can work is to know ahead of schedule, how many buckets will be needed. From the example above, I'm assuming that there are at least 55 buckets...all initialized to some null value. When you get 23, simply toggle bit 23 or set array[23] to 1 etc. etc. When you hit 10, you are done with the list and they are all sorted (you must skip NULLS when printing). Hash functions are very nice, but they many limitations... ---- Quote #4 Phil Dietz " " 231b3678@fergvax.unl.edu -- Invisible Man University of Nebraska
staale@stud.cs.uit.no (Staale Schwenke) (06/07/91)
In article <8235@oasys.dt.navy.mil>, tdsmith@oasys.dt.navy.mil (Timothy Smith) writes: |> In article <193e8efd.ARN1453@pilhuhn.ka.sub.org> hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) writes: |> >Imagine that You have 50 States. Bucket sort means now sorting the letters |> >according to the name of the State in one of 50 Boxes (or Buckets) labeled |> >with the name of the State. Going once through the data costs O(n); adding |> >an element to the head of the list costs O(1) -> You get linear (O(n)) running |> >time. |> |> What? Start with an unsorted list of n objects (or pointers to objects, |> same thing...) Is there a sort algorithm which is o(n)? If so, use |> it to sort (23 41 55 12 11 9 10) with only 7 moves. I'm skeptical! |> ^^^^^ |> Tim Hm.. Reads Assuming , like in the original example, you have a finite number of different keys e.g. 0-100, this could be done by going once through the data. Based on the value each number would be moved into a bucket. (F.ex. an array [0..100] if identical keys were not allowed). -- ------------------------------------------------------------------------ Staale Schwenke E-mail: staale@stud.cs.uit.no ------------------------------------------------------------------------
ttobler@unislc.uucp (Trent Tobler) (06/14/91)
From article <8235@oasys.dt.navy.mil>, by tdsmith@oasys.dt.navy.mil (Timothy Smith): > In article <193e8efd.ARN1453@pilhuhn.ka.sub.org> hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) writes: >>Imagine that You have 50 States. Bucket sort means now sorting the letters >>according to the name of the State in one of 50 Boxes (or Buckets) labeled >>with the name of the State. Going once through the data costs O(n); adding >>an element to the head of the list costs O(1) -> You get linear (O(n)) running >>time. > > What? Start with an unsorted list of n objects (or pointers to objects, > same thing...) Is there a sort algorithm which is o(n)? If so, use > it to sort (23 41 55 12 11 9 10) with only 7 moves. I'm skeptical! > Except than o(n) does not mean n moves. o(n) means it takes exactly k*n with k constant. In your example, suppose the numbers are in the range of 0-255. One o(n) sort that I can think of goes like this. We have an array of 256 elements labeled A(x) which can hold a range of 0 up to the maximum size of an array we wish to sort. To sort, simply initialize this array to all 0, then for each item to sort, increment to corresponding element. For the example you give, A(x) would be A(0)=0, A(1)=0, ..., A(9)=1, A(10)=1, A(11)=1, ... A(254)=0, A(255)=0 Then, go though this array, starting from 0 and working to 256, and store A(x) x's into the original array, ie.. no 0's, no 1's, ..., one 9, one 10, one 11, ... no 254's, no 255's. and you have the original array, sorted. ( 9 10 11 12 23 41 55 ) This method takes 2 * 256 + 2 * n steps. In otherwords, it is o(n) -- Trent Tobler - ttobler@csulx.weber.edu
tdsmith@oasys.dt.navy.mil (Timothy Smith) (06/14/91)
In article <1991Jun13.175106.6902@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes: >From article <8235@oasys.dt.navy.mil>, by tdsmith@oasys.dt.navy.mil (Timothy Sm >ith): >> >> Start with an unsorted list of n objects (or pointers to objects, >> same thing...) Is there a sort algorithm which is o(n)? If so, use >> it to sort (23 41 55 12 11 9 10) with only 7 moves. I'm skeptical! >> >Except than o(n) does not mean n moves. o(n) means it takes exactly >k*n with k constant. Oops! Guess I was typing a bit too quickly. In your example, suppose the numbers are in the range >of 0-255. One o(n) sort that I can think of goes like this. > > We have an array of 256 elements labeled A(x) which can hold a range of >0 up to the maximum size of an array we wish to sort... {...stuff...} >Then, go though this array, starting from 0 and working to 256, and >store A(x) x's into the original array, ie.. {...more stuff...} >This method takes 2 * 256 + 2 * n steps. In otherwords, it is o(n) > >-- > Trent Tobler - ttobler@csulx.weber.edu Let m be the number of buckets. I get O(2*m+2*n) => O(m+n) => O(max(m,n)) => max(O(n),O(m)) The problem as I see it is that the bucket range has to be defined ahead of time. For reccuring problems this is fine, since m can be fixed. But for arbitrary problems it is not so clear. For example, sorting (3 1 2) can be done with 3 buckets, but (10,000 1 2) requires 10,000 buckets. Are both problems O(3)? In theory, yes. In practice, no. A key variable has been neglected. For real numbers m is infinite. I conclude combsort is not a general purpose sorting algorithm, just a special case integer sort over a finite set of input possibilities. In THEORY combsort is O(n), but theory sometimes has little relation to practicality. If m is O(n) then the sort is O(n), otherwise the analysis is misleading. If m >> n then combsort is O(1)! AND, if m >> n^2 then selection sort wil beat it, even though selection sort is O(n^2)! I bring this up because this isn't comp.theory, so O(n) could be taken out of context. - Complexity is not a quantitative measure of utility between algorithms, it is a qualitatively estimate of the time for different sized runs with the same algorithm. - Two algorithms with the same complexity may have run times that differ by orders of magnitude. - Complexity claims are sensitive to how the problem is posed. Sometimes the worst case complexity is quoted, sometimes the average, and sometimes the most likely. This becomes a problem when the worst case for one is compared with the average for another. - There are no general purpose sorts which do better than O(n*logn). - There are some special purpose integer sorts that are O(n). - If the input domain is restricted to n << m combsort becomes O(1), i.e. runs in constant time. It also becomes a very inefficient algorithm. (for the above example, bubblesort uses aprox 4 moves to sort (10,000 2 1), combsort uses aprox 20,000 moves. On (10,000 5,000 4 3 2 1), a problem which is twice as big, bublesort uses aprox 25 moves, combsort 20,000.) Tim Smith
mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) (06/16/91)
In article <8454@oasys.dt.navy.mil> tdsmith@oasys.dt.navy.mil (Timothy Smith) writes:
The problem as I see it is that the bucket range has to be defined
ahead of time. For reccuring problems this is fine, since m can be
fixed. But for arbitrary problems it is not so clear.
Yup, but there's a way around that. Choose some convenient size chunk,
and combsort the high-order chunk of that size in each key. You've
just partitioned the elements so that each element is in the partition
it will be in when correctly sorted. Sort each bucket by the second
chunk in the keys, producing a second level of buckets. Continue down
the keys until either the buckets are singleton sets, or you run out
of key (at which time all the keys in any bucket will be equal). The
net result is that you've looked at each chunk a fixed number of times
(once if you do it BFI, a few more if you finesse it).
For real numbers m is infinite. I conclude combsort is not a general
purpose sorting algorithm, just a special case integer sort over a finite
set of input possibilities.
Well, the above outlines a variant of combsort that applies to
arbitrary keys. It's generally known as a "radix sort". For most
computers (like an Amiga), "bytes" are the obvious convenient size
chunk. That's what the implementation I've got uses.
IN THEORY combsort is O(n), but theory sometimes has little relation to
practicality.
In theory, a radix sort is O(c), where c is the number of chunks. A
combsort is a radixsort where c is the key size. This isn't practical
for all keys. However, choosing a practical chunk size is always
possible, and the resulting implementation works.
- There are no general purpose sorts which do better than O(n*logn).
False. See the above. It's a general purpose algorithm, and it's
always better (in the theoretical sense) than O(n*logn).
<mike
--
Kiss me with your mouth. Mike Meyer
Your love is better than wine. mwm@pa.dec.com
But wine is all I have. decwrl!mwm
Will your love ever be mine?GUTEST8@cc1.kuleuven.ac.be (Ives Aerts) (06/18/91)
>> - There are no general purpose sorts which do better than O(n*logn). >False. See the above. It's a general purpose algorithm, and it's >always better (in the theoretical sense) than O(n*logn). We have seen this year (I just did my exam for it last week) that there is no GENERAL sorting algorithm which is better than O(n*logn) We have also seen the proof to this theorem but I'm not going to repeat it here since I forgot it :-) It has something to do with sort trees. By GENERAL I mean that the algorithm must be able to sort anything (including things with variable length (which can of course be forced if you extend all items to the same maximum length)).
nj@magnolia.Berkeley.EDU (Narciso Jaramillo) (06/19/91)
In article <91169.133303GUTEST8@cc1.kuleuven.ac.be> GUTEST8@cc1.kuleuven.ac.be (Ives Aerts) writes:
We have seen this year (I just did my exam for it last week) that there
is no GENERAL sorting algorithm which is better than O(n*logn)
By GENERAL I mean that the algorithm must be able to sort anything
(including things with variable length (which can of course be
forced if you extend all items to the same maximum length)).
To be more precise, the theorem holds only for algorithms which sort
by comparing keys to each other. These algorithms rely only on the
keys being linearly ordered, and the ability to do one comparison in
O(1) time. Algorithms like Radix Sort make extra assumptions about
the keys (in this case, that they are numbers and can be broken up
into digits), and thus can achieve better worst case complexity (but
at the cost of extra space utilization in this case).
njmwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) (06/19/91)
In article <NJ.91Jun18111231@magnolia.Berkeley.EDU> nj@magnolia.Berkeley.EDU (Narciso Jaramillo) writes: In article <91169.133303GUTEST8@cc1.kuleuven.ac.be> GUTEST8@cc1.kuleuven.ac.be (Ives Aerts) writes: We have seen this year (I just did my exam for it last week) that there is no GENERAL sorting algorithm which is better than O(n*logn) By GENERAL I mean that the algorithm must be able to sort anything (including things with variable length (which can of course be forced if you extend all items to the same maximum length)). To be more precise, the theorem holds only for algorithms which sort by comparing keys to each other. These algorithms rely only on the keys being linearly ordered, and the ability to do one comparison in O(1) time. Algorithms like Radix Sort make extra assumptions about the keys (in this case, that they are numbers and can be broken up into digits), and thus can achieve better worst case complexity (but at the cost of extra space utilization in this case). Actually, the radix sort assumption is slightly more general than that. It assumes that you can address "subkeys" that are small enough to be bucket sorted on your machine. This assumption is true for any octet addressable machine with more than a few K octets of ram. Note that a fully general implementation inside of those constraints requires that you allow specification of the order to sort subkeys (e.g. - byte 3, then byte 1, then byte 2, then byte 0), as well as an ordering on each subkey (e.g. - for each subkey, you provide a lookup table that gives the sort order for that subkey). <mike -- And then up spoke his own dear wife, Mike Meyer Never heard to speak so free. mwm@pa.dec.com "I'd rather a kiss from dead Matty's lips, decwrl!mwm Than you or your finery."