home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mitsch75.zip / scheme-7_5_17-src.zip / scheme-7.5.17 / src / runtime / qsort.scm < prev    next >
Text File  |  1999-01-02  |  2KB  |  76 lines
  1. #| -*-Scheme-*-
  2.  
  3. $Id: qsort.scm,v 14.4 1999/01/02 06:11:34 cph Exp $
  4.  
  5. Copyright (c) 1988-1999 Massachusetts Institute of Technology
  6.  
  7. This program is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 2 of the License, or (at
  10. your option) any later version.
  11.  
  12. This program is distributed in the hope that it will be useful, but
  13. WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15. General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program; if not, write to the Free Software
  19. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20. |#
  21.  
  22. ;;;; Quick Sort
  23. ;;; package: ()
  24.  
  25. (declare (usual-integrations))
  26.  
  27. (define (quick-sort vector predicate)
  28.   (if (vector? vector)
  29.       (quick-sort! (vector-copy vector) predicate)
  30.       (vector->list (quick-sort! (list->vector vector) predicate))))
  31.  
  32. (define (quick-sort! vector predicate)
  33.   (define (outer-loop l r)
  34.     (if (fix:> r l)
  35.     (if (fix:= r (fix:+ l 1)) 
  36.         (if (predicate (vector-ref vector r)
  37.                (vector-ref vector l))
  38.         (exchange! l r))
  39.         (let ((lth-element (vector-ref vector l)))
  40.  
  41.           (define (increase-i i)
  42.         (if (or (fix:> i r)
  43.             (predicate lth-element (vector-ref vector i)))
  44.             i
  45.             (increase-i (fix:+ i 1))))
  46.  
  47.           (define (decrease-j j)
  48.         (if (or (fix:<= j l)
  49.             (not (predicate lth-element (vector-ref vector j))))
  50.             j
  51.             (decrease-j (fix:- j 1))))
  52.  
  53.           (define (inner-loop i j)
  54.         (if (fix:< i j)        ;used to be <=
  55.             (begin
  56.               (exchange! i j)
  57.               (inner-loop (increase-i (fix:+ i 1))
  58.                   (decrease-j (fix:- j 1))))
  59.             (begin
  60.               (if (fix:> j l)
  61.               (exchange! j l))
  62.               (outer-loop (fix:+ j 1) r)
  63.               (outer-loop l (fix:- j 1)))))
  64.  
  65.           (inner-loop (increase-i (fix:+ l 1))
  66.               (decrease-j r))))))
  67.  
  68.   (define-integrable (exchange! i j)
  69.     (let ((ith-element (vector-ref vector i)))
  70.       (vector-set! vector i (vector-ref vector j))
  71.       (vector-set! vector j ith-element)))
  72.  
  73.   (if (not (vector? vector))
  74.       (error:wrong-type-argument vector "vector" 'QUICK-SORT!))
  75.   (outer-loop 0 (fix:- (vector-length vector) 1))
  76.   vector)