Сортировка Шелла - Lisp

Формулировка задачи:

Добрый день, помогите плиз реализовать сортировку Шелла методом Кнута

Решение задачи: «Сортировка Шелла»

Листинг программы

(defun gap-insertion-sort (array predicate gap)
  (let ((length (length array)))
    (if (< length 2) array
      (do ((i 1 (1+ i))) ((eql i length) array)
        (do ((x (aref array i))
             (j i (- j gap)))
            ((or (minusp (- j gap))
                 (not (funcall predicate x (aref array (1- j)))))
             (setf (aref array j) x))
          (setf (aref array j) (aref array (- j gap))))))))
 
(defconstant +gaps+
  '(9841 3280 1093 364 121 40 13 4 1)
  "The best sequence of gaps, according to Donald E. Knuth.")
 
(defun shell-sort (array predicate &optional (gaps +gaps+))
  (assert (eql 1 (car (last gaps))) (gaps)
    "Last gap of ~w is not 1." gaps)
  (dolist (gap gaps array)
    (gap-insertion-sort array predicate gap)))
 
> (shell-sort #(5 3 8 1 9 3 4 7) #'<)
#(1 3 3 4 5 7 8 9)

Объяснение кода листинга программы

В этом коде реализована сортировка Шелла для массива чисел. Сначала определяются две функции: gap-insertion-sort и shell-sort. gap-insertion-sort - это вспомогательная функция, которая реализует алгоритм сортировки с использованием «пробелов» (gaps). Она принимает три аргумента: массив, предикат и «пробел». Предикат используется для сравнения элементов, а «пробел» определяет, на сколько позиций смещаются элементы при каждой итерации. Функция shell-sort принимает массив, предикат и список «пробелов». Она сначала проверяет, что последний «пробел» равен 1, иначе выводит сообщение об ошибке. Затем она перебирает все «пробелы» из списка, начиная с первого, и для каждого из них вызывает функцию gap-insertion-sort. В основной части кода вызывается функция shell-sort с аргументами (5 3 8 1 9 3 4 7)’ и#'<)'. Результатом будет отсортированный массив: (1 3 3 4 5 7 8 9).