[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scratch/timsort 8ef42e085b: Add more sorting unit tests
From: |
Andrew G Cohen |
Subject: |
scratch/timsort 8ef42e085b: Add more sorting unit tests |
Date: |
Thu, 17 Mar 2022 04:52:25 -0400 (EDT) |
branch: scratch/timsort
commit 8ef42e085be82a88ed01dc449b26f8bc582c149e
Author: Andrew G Cohen <cohen@andy.bu.edu>
Commit: Andrew G Cohen <cohen@andy.bu.edu>
Add more sorting unit tests
* test/src/fns-tests.el (fns-tests-sort): New sorting unit tests.
---
test/src/fns-tests.el | 46 ++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 46 insertions(+)
diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el
index 723ef4c710..2623b4c1b9 100644
--- a/test/src/fns-tests.el
+++ b/test/src/fns-tests.el
@@ -204,6 +204,52 @@
[-1 2 3 4 5 5 7 8 9]))
(should (equal (sort (vector 9 5 2 -1 5 3 8 7 4) (lambda (x y) (> x y)))
[9 8 7 5 5 4 3 2 -1]))
+ ;; Sort a reversed list and vector.
+ (should (equal
+ (sort (reverse (number-sequence 1 1000)) (lambda (x y) (< x y)))
+ (number-sequence 1 1000)))
+ (should (equal
+ (sort (reverse (vconcat (number-sequence 1 1000)))
+ (lambda (x y) (< x y)))
+ (vconcat (number-sequence 1 1000))))
+ ;; Sort a constant list and vector.
+ (should (equal
+ (sort (make-vector 100 1) (lambda (x y) (> x y)))
+ (make-vector 100 1)))
+ (should (equal
+ (sort (append (make-vector 100 1) nil) (lambda (x y) (> x y)))
+ (append (make-vector 100 1) nil)))
+ ;; sort a long list and vector with every pair reversed.
+ (let ((vec (make-vector 100000 nil))
+ (logxor-vec (make-vector 100000 nil)))
+ (dotimes (i 100000)
+ (aset logxor-vec i (logxor i 1))
+ (aset vec i i))
+ (should (equal
+ (sort logxor-vec (lambda (x y) (< x y)))
+ vec))
+ (should (equal
+ (sort (append logxor-vec nil) (lambda (x y) (< x y)))
+ (append vec nil))))
+ ;; sort a list and vector with seven swaps
+ (let ((vec (make-vector 100 nil))
+ (swap-vec (make-vector 100 nil)))
+ (dotimes (i 100)
+ (aset vec i (- i 50))
+ (aset swap-vec i (- i 50)))
+ (mapc (lambda (p)
+ (let ((tmp (elt swap-vec (car p))))
+ (aset swap-vec (car p) (elt swap-vec (cdr p)))
+ (aset swap-vec (cdr p) tmp)))
+ '((48 . 94) (75 . 77) (33 . 41) (92 . 52)
+ (10 . 96) (1 . 14) (43 . 81)))
+ (should (equal
+ (sort (copy-sequence swap-vec) (lambda (x y) (< x y)))
+ vec))
+ (should (equal
+ (sort (append swap-vec nil) (lambda (x y) (< x y)))
+ (append vec nil))))
+ ;; Check for sorting stability.
(should (equal
(sort
(vector
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- scratch/timsort 8ef42e085b: Add more sorting unit tests,
Andrew G Cohen <=