Сортировка списка по номеру и символу

У вас есть в основном два варианта:

• определить функцию сравнения двух элементов (x0 y0) и (x1 y1), которая возвращает T, если:

  • x0 < x1 или
  • x0 и x1 эквивалентны [*] и y0 <' y1.

  Вы также можете обобщить это решение, определив функции более высокого порядка, которые принимают список тестовых и ключевых параметров и объединяют их для создания функции сравнения, которая применяет их все к двум значениям.

  [*] эквивалентность не определяется ни a < b, ни b < a в общем случае, когда < является функцией сравнения, предоставляемой пользователем.

• отсортируйте список один раз, чтобы сравнить соответствующие вторые поля записей, затем вызовите stable-sort результат для сортировки по первому полю: вы должны начать с наименее значимого поля (изменение порядка применения сортировки меняет результаты). Например:

  ((1 c) (2 b) (0 a) (1 b))
  

  сортировать по второму полю #'string<

  ((0 a) (1 b) (2 b) (1 c))
  

  затем стабильная сортировка по первому полю #'<

  ((0 a) (1 b) (1 c) (2 b))    #### RES 1
  

  Результат будет следующим, если сначала отсортировать по первому полю:

  ((0 a) (1 c) (1 b) (2 b))
  

  Затем (стабильно) по секунде:

  ((0 a) (1 b) (2 b) (1 c))    #### RES 2
  

  При вызове stable-sort, когда первое поле двух элементов равно, стабильность сортировки гарантирует, что они будут продолжать сортироваться по второму полю. Вы можете применить stable-sort несколько раз, если у вас есть больше полей для сравнения.

Будьте осторожны, в Common Lisp sort изменяет ввод.

Как говорит coredump, поскольку вам действительно нужна функция сравнения списков, хорошим подходом является мета-вещь: не пишите ее, а напишите функцию, которая создает функции, сравнивающие списки. Вот такая функция:

(defun make-list-comparator (&rest predicates)
  (labels ((tails< (l1t l2t pt)
             (let ((< (first pt))
                   (e1 (first l1t))
                   (e2 (first l2t)))
               (cond
                ((funcall < e1 e2) t)
                ((funcall < e2 e1) nil)
                ((and (null l1t) (null l2t) (null pt)) nil)
                ((or (null l1t) (null l2t) (null pt))
                 (error "crashed into the end"))
                (t (tails< (rest l1t) (rest l2t) (rest pt)))))))
    (lambda (l1 l2)
      (tails< l1 l2 predicates))))

И сейчас

> (sort (copy-list '((1 b) (1 a) (2 D) (1 z) (1 t) (2 a) (1)))
        (make-list-comparator
         #'<
         (lambda (s1 s2)
           (string< (string s1) (string s2)))))
((1 a) (1 b) (1 t) (1 z) (2 a) (2 d) (3 n))