sort-aux.lsp 1.16 KB
Newer Older
1 2 3 4 5
;-*- Mode:     Lisp -*-
;;;; Author:   Paul Dietz
;;;; Created:  Thu Jul 17 06:42:27 2003
;;;; Contains: Routines for testing SORT, NSORT

6

7 8 9 10 11 12

(defun my-numeric-sort (list)
  "Sort (nondestructively) a list of reals."
  (if (null (cdr list))
      list
    (let* ((len2 (ash (length list) -1))
sds's avatar
sds committed
13 14
           (l1 (my-numeric-sort (subseq list 0 len2)))
           (l2 (my-numeric-sort (subseq list len2))))
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
      (my-numeric-merge l1 l2))))

(defun my-numeric-merge (l1 l2)
  (cond
   ((null l1) l2)
   ((null l2) l1)
   ((<= (car l1) (car l2))
    (cons (car l1) (my-numeric-merge (cdr l1) l2)))
   (t
    (cons (car l2) (my-numeric-merge l1 (cdr l2))))))

(defun generate-random-sort-test (n m)
  (loop for i below n collect (random m)))

(defun random-sort-test (n m reps)
  (loop
   for i below reps
   for list = (generate-random-sort-test (random n) m)
   unless (equal (my-numeric-sort list)
sds's avatar
sds committed
34
                 (sort (copy-seq list) #'<))
35 36 37 38 39 40 41
   collect list))

(defun random-stable-sort-test (n m reps)
  (loop
   for i below reps
   for list = (generate-random-sort-test (random n) m)
   unless (equal (my-numeric-sort list)
sds's avatar
sds committed
42
                 (stable-sort (copy-seq list) #'<))
43
   collect list))