home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / mutt / qsort.mut < prev    next >
Text File  |  1988-03-01  |  2KB  |  55 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. (defun
  11.   Qsort (list)(int m n)(pointer defun swap cmp)
  12.   {
  13.     (int i j)
  14.  
  15.     (if (>= m n)(done))
  16.     (i m)(j (+ n 1))
  17.     (while TRUE
  18.     {
  19.       (while { (+= i 1)(and (<= i n) (< (cmp list i m) 0)) } ())
  20.       (while { (-= j 1)(> (cmp list j m) 0) } ())
  21.       (if (< i j) (swap list i j) (break))
  22.     })
  23.     (swap list m j)
  24.     (Qsort list m (- j 1) swap cmp)
  25.     (Qsort list (+ j 1) n swap cmp)
  26.   }
  27. )
  28.  
  29. (defun
  30.   swap (array int list 1)(int a b)    ; swap 2 elements
  31.   {
  32.     (int tmp)
  33.     (tmp (list a))(list a (list b))(list b tmp)
  34.   }
  35.   cmp (array int list 1)(int a b)    ; compare 2 elements
  36.     { (- (list a)(list b)) }
  37. )
  38.  
  39. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  40. ;;;;;;;;;;;;;;;;;  test ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  41. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  42.  
  43. (include random.mut)
  44.  
  45. (array int list 501) (int n j)
  46. (n (atoi (ask "n = ")))
  47.  
  48. ;(srand 123)
  49. (for (j 0) (< j n)(+= j 1) (list j (rand)))
  50.  
  51. (for (j 0)(< j n)(+= j 1) (msg "list[" j "] = " (list j)))
  52. (Qsort list 0 (- n 1) (floc swap) (floc cmp))
  53. (msg "--------------------------")
  54. (for (j 0)(< j n)(+= j 1) (msg "list[" j "] = " (list j)))
  55.