home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / m / me_cd25.zip / MC2MUTT.ZIP / QSORT.MUT < prev    next >
Lisp/Scheme  |  1992-11-09  |  2KB  |  91 lines
  1.     ; Quick sort.  From Horowitz & Sahni pg 347
  2.     ; Sort list[m..n] into assending order
  3.  
  4.     ; swap is a routine that interchanges list[a] with list[b]
  5.     ; cmp compares list[a] with list[b] and returns:
  6.     ;    negative if list[a] < list[b]
  7.     ;    positive if list[a] > list[b]
  8.     ;    zero     if list[a] = list[b]
  9.  
  10.     ; Modeled (a bit) after the lib C qsort()
  11. (defun
  12.   Qsort (list-to-sort)(int m n)(pointer defun swap cmp)
  13.   {
  14.     (int i j)
  15.  
  16.     (if (>= m n) (done))    ;; end the recursion
  17.     (i m) (j (+ n 1))
  18.     (while TRUE
  19.     {
  20.       (while { (+= i 1)(and (<= i n) (< (cmp list-to-sort i m) 0)) } ())
  21.       (while { (-= j 1)(> (cmp list-to-sort j m) 0) } ())
  22.       (if (< i j) (swap list-to-sort i j) (break))
  23.     })
  24.     (swap list-to-sort m j)
  25.     (Qsort list-to-sort m (- j 1) swap cmp)
  26.     (Qsort list-to-sort (+ j 1) n swap cmp)
  27.   }
  28. )
  29.     ; swap and cmp routines for arrays of ints
  30. (defun
  31.   swap (array int list-to-sort 1)(int a b)    ; swap 2 elements
  32.   {
  33.     (int tmp)
  34.     (tmp (list-to-sort a)) (list-to-sort a (list-to-sort b))
  35.     (list-to-sort b tmp)
  36.   }
  37.   cmp (array int list-to-sort 1)(int a b)    ; compare 2 elements
  38.     { (- (list-to-sort a) (list-to-sort b)) }
  39. )
  40.  
  41.  
  42. (defun        ;; Quick sort an array of ints
  43.  QSort(array int vector 1)(int m n)
  44.  {
  45.    (int i j t k)
  46.  
  47. (msg "==> " m " " n)
  48.    (if (>= m n)(done))
  49.    (i m)(j (+ n 1))(k (vector m))
  50.    (while TRUE
  51.    {
  52.      (while { (+= i 1)(< (vector i) k)} ())
  53.      (while { (-= j 1)(> (vector j) k)} ())
  54.      (if (< i j)
  55.      {
  56.     (t (vector i))(vector i (vector j))(vector j t)
  57.      }
  58.      (break))
  59.    })
  60.    (t (vector m))(vector m (vector j))(vector j t)
  61.    (QSort vector m (- j 1))
  62.    (QSort vector (+ j 1) n)
  63.  }
  64. )
  65.  
  66. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  67. ;;;;;;;;;;;;;;;;;  test ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  68. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  69.  
  70. (const NUMBER    0x03)
  71.  
  72. (include random.mut)
  73.  
  74. (array int list-to-sort 501) (int n j)
  75.  
  76. (defun MAIN
  77. {
  78.   (n (convert-to NUMBER (ask "n = ")))
  79.  
  80.   ;(srand 123)
  81.   (for (j 0) (< j n)(+= j 1) (list-to-sort j (rand)))
  82.  
  83.   (for (j 0)(< j n)(+= j 1) (msg "Random list[" j "] = " (list-to-sort j)))
  84.  
  85. ;  (QSort list-to-sort 0 (- n 1))
  86.   (Qsort list-to-sort 0 (- n 1) (floc swap) (floc cmp))
  87.  
  88.   (msg "--------------------------")
  89.   (for (j 0)(< j n)(+= j 1) (msg "Sorted list[" j "] = " (list-to-sort j)))
  90. })
  91.