Написать программу сортировки списка методом Шелла - Lisp

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

Написать программу сортировки списка методом Шелла. Вычисление последовательности шагов сортировки производится методом Р. Седжвика. Нельзя использовать функции SET, SETQ, SETF и циклы. Может у кого-то что-то есть?

Решение задачи: «Написать программу сортировки списка методом Шелла»

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

(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 (< (- j gap) 0)
                 (not (funcall predicate x (aref array (1- j)))))
             (setf (aref array j) x))
          (setf (aref array j) (aref array (- j gap))))))))
 
(defconstant +gaps+
  '(1750 701 301 132 57 23 10 4 1)
  "The best sequence of gaps, according to Marcin Ciura.")
 
(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)))

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

В коде присутствуют две функции: gap-insertion-sort и shell-sort. Функция gap-insertion-sort принимает три аргумента: array, predicate и gap.

Если длина массива меньше двух, то возвращается исходный массив, так как он уже отсортирован.
Иначе, выполняется следующая последовательность действий: a. Перебираются все элементы массива, начиная с первого. b. На каждой итерации выполняется следующая последовательность действий: i. Если текущий элемент меньше следующего, то они меняются местами. ii. Уменьшается значение переменной gap на единицу. iii. Если значение переменной gap стало меньше или равно нулю, то выполняется следующая последовательность действий: i. Увеличивается значение переменной i на единицу. ii. Если i равно длине массива, то выполняется завершающая сортировка. iii. Если следующий элемент больше текущего, то они меняются местами. iv. Увеличивается значение переменной j на единицу. v. Если j меньше значения переменной gap, то выполняется следующая последовательность действий: i. Если следующий элемент меньше текущего, то они меняются местами. ii. Увеличивается значение переменной j на единицу. iii. Если j меньше значения переменной gap, то выполняется завершающая сортировка. iv. Если следующий элемент больше текущего, то они меняются местами. c. Если длина массива равна двум, то выполняется завершающая сортировка. Функция shell-sort принимает три аргумента: array, predicate и gaps.
Проверяется, что последний элемент в переменной gaps равен единице. Если это не так, то выводится сообщение об ошибке.
Перебираются все элементы в переменной gaps.
Для каждого элемента в переменной gaps вызывается функция gap-insertion-sort с аргументами array и predicate.