LISP - Sorting Strings

Lisp - Sorting Strings and Sequences

Common Lisp provides a powerful sort function for ordering sequences. This function is flexible and can sort various sequence types, such as lists and vectors, based on a provided predicate function. In this chapter, we’ll explore how to sort strings effectively.

The sort and stable-sort Functions

The primary function for sorting is sort. It takes two main arguments: the sequence to be sorted and a predicate function that determines the order.

Important: sort is a destructive function. It modifies the original sequence in place. If you need to preserve the original sequence, you must sort a copy.

;; To sort a list non-destructively, sort a copy of it.
(sort (copy-list original-list) #'<)

;; To sort any sequence non-destructively, use copy-seq.
(sort (copy-seq original-sequence) #'<)

Common Lisp also provides stable-sort, which works identically but guarantees that the relative order of elements considered equal by the predicate is preserved.

Example: Case-Insensitive String Sorting

To sort strings without regard to case, you use the string-lessp predicate. It compares two strings lexicographically, ignoring case differences.

main.lisp

;; Define a list of strings to be sorted.
(defvar *fruits* '("banana" "Apple" "Orange" "cherry"))

;; Sort a copy of the list case-insensitively.
(let ((sorted-fruits (sort (copy-list *fruits*) #'string-lessp)))
  (format t "Original: ~a~%" *fruits*)
  (format t "Sorted (case-insensitive): ~a~%" sorted-fruits))

Output

When you execute the code, it returns the following result:

Original: ("banana" "Apple" "Orange" "cherry")
Sorted (case-insensitive): ("Apple" "banana" "cherry" "Orange")

Example: Case-Sensitive String Sorting

For case-sensitive sorting, use the string< predicate. With this predicate, uppercase letters are typically considered “less than” lowercase letters.

main.lisp

;; Use the same list of fruits.
(defvar *fruits* '("banana" "Apple" "Orange" "cherry"))

;; Sort a copy case-sensitively.
(let ((sorted-fruits (sort (copy-list *fruits*) #'string<)))
  (format t "Case-Sensitive Sort: ~a~%" sorted-fruits))

;; Let's try it on a vector as well.
;; Note that the output will be a vector: #(...)
(let ((fruit-vector (vector "banana" "Apple" "Orange" "cherry")))
    (format t "Sorted Vector: ~a~%" (sort fruit-vector #'string<)))

Output

When you execute the code, the output reflects case-sensitive ordering:

Case-Sensitive Sort: ("Apple" "Orange" "banana" "cherry")
Sorted Vector: #("Apple" "Orange" "banana" "cherry")

Best Practices for Sorting

• Be Mindful of Destruction: Always be aware that sort modifies its argument. If the original data is important, (sort (copy-seq ...)) is your friend.
• Choose the Right Predicate: Use string-lessp and string-greaterp for user-facing, case-insensitive sorting. Use string< and string> for strict, case-sensitive lexicographical sorting.
• Consider Stability: If the original relative order of equal items matters, use stable-sort instead of sort.