LISP - Sorting a List

Lisp - Sorting Sequences

Common Lisp provides powerful and generic functions for sorting sequences like lists and vectors. The primary functions are sort and stable-sort. Understanding their behavior, especially their destructive nature, is key to using them correctly.

sort and stable-sort: The Destructive Sorters

Both sort and stable-sort modify the sequence passed to them directly. This is called a destructive operation. It’s efficient because it avoids allocating a new sequence, but it means your original data will be changed.

The syntax is: (sort sequence predicate &key key)

• sequence: The list or vector to be sorted.
• predicate: A function that takes two arguments and returns true if the first argument should come before the second. Common predicates are #< for numbers and string< for strings.
• stable-sort vs sort: stable-sort guarantees that the relative order of elements considered equal by the predicate is preserved. sort makes no such guarantee.

Example: Destructive Sort

(let ((numbers '(4 3 7 2 1 8 3)))
  (print (format nil "Original list: ~a" numbers))

  ;; Sort the list in place.
  (sort numbers #'<)

  (print (format nil "List after sort: ~a" numbers)))

;; Output:
;; "Original list: (4 3 7 2 1 8 3)"
;; "List after sort: (1 2 3 3 4 7 8)"

Non-Destructive Sorting

To sort a sequence without modifying the original, you must first create a copy. The generic way to do this is with copy-seq.

(let ((original-data '("Apple" "Coconut" "Banana" "Orange")))

  ;; Create a sorted copy, leaving the original untouched.
  (let ((sorted-data (sort (copy-seq original-data) #'string<)))
    (print (format nil "Original: ~a" original-data))
    (print (format nil "Sorted Copy: ~a" sorted-data)))
)

;; Output:
;; "Original: (\"Apple\" \"Coconut\" \"Banana\" \"Orange\")"
;; "Sorted Copy: (\"Apple\" \"Banana\" \"Coconut\" \"Orange\")"

Advanced Sorting with :key

The :key argument allows you to specify a function to be called on each element before it’s passed to the predicate. This is essential for sorting complex data structures.

Example: Sorting a List of Objects

Let’s define a simple structure for a product and sort a list of products by price.

;; Define a simple product structure
(defstruct product name price)

(let ((inventory (list (make-product :name "Laptop" :price 1200)
                     (make-product :name "Mouse" :price 25)
                     (make-product :name "Keyboard" :price 75))))

  ;; Sort by price (low to high)
  (let ((sorted-inventory (sort (copy-list inventory) #'< :key #'product-price)))
    (loop for p in sorted-inventory
          do (format t "~a: $~a~%" (product-name p) (product-price p)))))

;; Output:
;; Mouse: $25
;; Keyboard: $75
;; Laptop: $1200

Sorting by Multiple Criteria

To sort by a primary key, and then by a secondary key for items where the primary key is equal, you should use stable-sort. The trick is to sort by the least significant key first, and then by the most significant key.

Example: Sorting People by Age, then Name

(defstruct person name age)

(let ((people (list (make-person :name "Bob" :age 30)
                  (make-person :name "Alice" :age 25)
                  (make-person :name "Charlie" :age 30))))

  ;; To sort by age (primary) then name (secondary), we do two stable sorts:

  ;; 1. Sort by the secondary key (name) first.
  (setf people (stable-sort people #'string< :key #'person-name))
  ;; -> people is now ((#S(PERSON :NAME "Alice" :AGE 25)) (#S(PERSON :NAME "Bob" :AGE 30)) (#S(PERSON :NAME "Charlie" :AGE 30)))

  ;; 2. Sort the result by the primary key (age).
  ;; Because stable-sort preserves order of equal elements,
  ;; Bob and Charlie (both 30) will remain in their alphabetical order.
  (setf people (stable-sort people #'< :key #'person-age))

  (loop for p in people do (print p)))

;; Final Output:
;; #S(PERSON :NAME "Alice" :AGE 25)
;; #S(PERSON :NAME "Bob" :AGE 30)
;; #S(PERSON :NAME "Charlie" :AGE 30)