home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 7042 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.3 KB
  1. Path: haapa.oulu.fi!not-for-mail
  2. From: tikarjal@haapa.oulu.fi (Timo Karjalainen)
  3. Newsgroups: comp.sys.amiga.programmer
  4. Subject: Re: Sorting a list
  5. Date: 7 Apr 1996 09:39:00 GMT
  6. Organization: University of Oulu
  7. Distribution: 'Net
  8. Message-ID: <4k82fk$f5s@ousrvr3.oulu.fi>
  9. References: <272.6650T63T1340@sn.no> <ZZNYYD.96Mar21121908@diku.dk>  <xUqu7MD1A7alz7@0dietmar.tomate.tng.oche.de>
  10. NNTP-Posting-Host: haapa.oulu.fi
  11. Mime-Version: 1.0
  12. Content-Type: text/plain; charset=iso-8859-1
  13. Content-Transfer-Encoding: 8bit
  14. X-Newsreader: TIN [UNIX 1.3 950824BETA PL0]
  15.  
  16. Dietmar Eilert (DIETMAR@TOMATE.TNG.OCHE.DE) wrote:
  17.  
  18. : You could use a simple modification of bubble sort to boost performance to
  19. : the speed of QuickSort: use a dynamic interval instead of comparing
  20. : neighbours only.
  21.  
  22. Another speedup would be to alternate walking through the items from head 
  23. to tail and vice versa. The worst caveat of bubblesort is that items that
  24. would belong to the head but are at the tail only move one position at a 
  25. time towards the head of the list - if the list is only processed from
  26. head to tail, and vice versa if it's done tail to head. By alternating
  27. both ways, the worst-case items should swim into their correct positions
  28. somewhat faster. 
  29.  
  30. The termination test is as usual: when either of the sort loops ends without
  31. any swaps, the list is ordered.
  32.  
  33. tikarjal
  34.  
  35.