quicksort.scm 881 B

12345678910111213141516171819202122232425262728293031
  1. (define (partition!* v j high i pivot)
  2. (if (< j high)
  3. (let ((j* (vector-ref v j)))
  4. (if (<= j* pivot)
  5. (let ((i* (vector-ref v (unbox i))))
  6. (vector-set! v (unbox i) j*)
  7. (vector-set! v j i*)
  8. (set-box! i (+ (unbox i) 1)))
  9. #f)
  10. (partition!* v (+ j 1) high i pivot))
  11. #f))
  12. (define (partition! v low high)
  13. (let ((pivot (vector-ref v high))
  14. (i (box low)))
  15. (partition!* v low high i pivot)
  16. (let ((high* (vector-ref v high))
  17. (i* (vector-ref v (unbox i))))
  18. (vector-set! v (unbox i) high*)
  19. (vector-set! v high i*)
  20. (unbox i))))
  21. (define (qsort!* v low high)
  22. (if (< low high)
  23. (let ((p (partition! v low high)))
  24. (qsort!* v low (- p 1))
  25. (qsort!* v (+ p 1) high))
  26. v))
  27. (define (qsort! v) (qsort!* v 0 (- (vector-length v) 1)))