Шейкерная сортировка в Lisp

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

Уже несколько недель пытаюсь реализовать алгоритм шейкерной сортировки в Lisp, но ничего не получается...Очень сложно после императивного программирования перейти к функциональному...Прошу очень помочь специалистов Lisp. Заранее благодарен

Решение задачи: «Шейкерная сортировка в Lisp»

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

;; Последний элемент списка
 
(defun last-el (lst) (car (last lst))) 
 
;; Предпоследний элемент списка
 
(defun plast-el (lst) (car (last (butlast lst)))) 
 
;; Проход вправо
 
(defun step-r (lst)
  (cond ((null (cdr lst)) lst)
        ((> (car lst) (cadr lst)) (cons (cadr lst) (step-r (cons (car lst) (cddr lst)))))
        (t (cons (car lst) (step-r (cdr lst))))))
 
;; Проход влево
 
(defun step-l (lst)
  (cond ((null (cdr lst)) lst)
        ((> (plast-el lst) (last-el lst)) (append (step-l (append (butlast (butlast lst)) (last lst))) (list (plast-el lst))))
        (t (append (step-l (butlast lst)) (last lst)))))
 
;; Шейкерная сортировка
 
(defun cocktail (lst &optional (n (length lst)))
 (cond ((<= n 1) lst)
       (t (let* ((l1 (step-l lst))
                 (l2 (step-r l1)))
          (append (list (car l2)) (cocktail (cdr (butlast l2)) (- n 2)) (last l2)))))) 
 
(cocktail '(1 8 2 1 4 0 7 2))
 
==> (0 1 1 2 2 4 7 8)

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

В этом коде реализована функция cocktail, которая выполняет шикерную сортировку списка. Эта функция принимает список и опциональный аргумент n, который указывает количество итераций сортировки. Если n не указан, то он вычисляется как длина списка. Функция step-r выполняет проход по списку вправо. Если список пуст или его первый элемент больше второго, то вызывается рекурсия с новым списком, состоящим из второго элемента исходного списка. В противном случае, первый элемент добавляется в новый список, и выполняется рекурсивный вызов для оставшейся части списка. Функция step-l выполняет проход по списку влево. Если список пуст или его последний элемент меньше предпоследнего, то вызывается рекурсия с новым списком, состоящим из предпоследнего элемента исходного списка. В противном случае, новый список формируется из оставшейся части списка, а последний элемент добавляется в конец. Функция last-el возвращает последний элемент списка. Функция plast-el возвращает предпоследний элемент списка. В функции cocktail выполняется рекурсивный вызов step-l и step-r, пока не будет достигнуто условие выхода из рекурсии, когда количество итераций равно n. Результатом работы функции является отсортированный список. Пример использования функции cocktail с аргументом '(1 8 2 1 4 0 7 2)' возвращает отсортированный список (0 1 1 2 2 4 7 8).