home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6428 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.7 KB
  1. Path: combo.ganesha.com!peterk
  2. From: peterk@combo.ganesha.com (Dr. Peter Kittel)
  3. Subject: Re: Sorting a list
  4. Newsgroups: comp.sys.amiga.programmer
  5. Reply-To: peterk@combo.ganesha.com
  6. References: <272.6650T63T1340@sn.no> <ZZNYYD.96Mar21121908@diku.dk>  <xUqu7MD1A7alz7@0dietmar.tomate.tng.oche.de>
  7. Message-ID: <peterk.0m19@combo.ganesha.com>
  8. Date: 27 Mar 96 00:22:03 MEZ
  9. Organization: Private Site
  10.  
  11. In article <xUqu7MD1A7alz7@0dietmar.tomate.tng.oche.de> DIETMAR@TOMATE.TNG.OCHE.DE (Dietmar Eilert) writes:
  12. >
  13. >You could use a simple modification of bubble sort to boost performance to
  14. >the speed of QuickSort: use a dynamic interval instead of comparing
  15. >neighbours only. In the first pass, you would compare element <a> to
  16. >element <a + distance> and swap them if the order is wrong. Distance is
  17. >reduced after processing all elements. To be continued until the distance
  18. >is <1> (standard bubble sort) and the order is correct.
  19. >
  20. >First pass:
  21. >
  22. >    distance = 3 * (elements - 1) / 4
  23. >
  24. >    if (distance == 0)
  25. >        distance = 1;
  26. >
  27. >Next pass:
  28. >
  29. >    if (distance = 3 * distance / 4)
  30. >        ready = FALSE;
  31.  
  32. Ah, one of my pet issues. This sounds very similar to the CombSort
  33. algorithm (Byte 4/1991, p. 315, S. Lacey, R. Box, developed on an Amiga!).
  34. They use an initial distance of (elements) and divide this number for
  35. every scan by 1.3, but of course don't go below 1. As an optimization,
  36. distances of 9 or 10 are avoided and replaced by 11. This way they also
  37. nearly reach QuickSort performance. Simply amazing.
  38.  
  39. -- 
  40. Best Regards, Dr. Peter Kittel       //    Visit  http://www.amiga.de
  41. Private Site in Frankfurt, Germany \X/  Email to: peterk@combo.ganesha.com
  42. Employed at AMIGA Technologies GmbH in Bensheim, Germany
  43.