Написать функцию сортировки списка методом прямого выбора

;; вспомогательная функция min2
 
(defun min2 (x y) (if (< x y) x y))
 
==> min2
 
(min2 5 6)
 
==> 5
 
(min2 5 -6)
 
==> -6
 
;; распространение min2 на произвольное к-во чисел
 
(defun min! (x) (cond ((= (length x) 1) (car x))
                      ((= (length x) 2) (min2 (car x) (cadr x)))
                      (t (min2 (car x) (min! (cdr x))))))
 
==> min!
 
;; Удаление из списка первого вхождения атома 
 
(defun remove (x a) (cond ((null x) nil)
                          ((EQ a (car x)) (cdr x))
                          (t (cons (car x) (remove (cdr x) a))))) 
 
==> remove
 
(remove '(11 22 33 11 22 33) 33)
 
==> (11 22 11 22 33)
 
;; Сортировка выбором
 
(defun sort (x) (cond ((null x) nil)
                      (t (cons (min! x) (sort (remove x (min! x) ))))))
 
(sort '(1 2 -3 33 12))
 
==> (-3 1 2 12 33)

;; Вспомогательная функция сравнения структур
 
(defun equal (x y) (COND ((ATOM x) (EQ x y)) 
                                   ((ATOM y) NIL) 
                                   ((equal (CAR x) (CAR y)) (equal (CDR x) (CDR y))) (T NIL)))
 
==> equal
 
(equal '(1 2 3) '(1 2 3))
 
==> T
 
(defun isSublist(lst s) 
    (cond ((null lst) nil)
          ((atom (car lst)) (OR (equal (car lst) s) (isSublist (cdr lst) s))) 
          (t (OR (equal (car lst) s) (isSublist (car lst) s) (isSublist (cdr lst) s))))) 
 
==> isSublist
 
(isSublist '(1 2 3) 2)
 
==> T
 
(isSublist '(1 2 3) 7)
 
==> NIL
 
(isSublist '(1 2 (((7))) 3) 7)
 
==> T
 
(isSublist '(1 2 (((7))) 3) '(7))
 
==> T

(explode 'fgh)
 
==> (f g h)

(defun mkListL (lst) (mapcar #'(lambda (x) (cons x (length (explode x)))) lst))
 
==> mkListL
 
(mkListL '(asd h dd w eeq sa sss dd d))
 
==> ((asd . 3) (h . 1) (dd . 2) (w . 1) (eeq . 3) (sa . 2) (sss . 3) (dd . 2) (d . 1))

(defun qsorta (x) 
    (COND ((NULL x) NIL) 
             (T (APPEND (qsorta (remove-if (FUNCTION (LAMBDA (z) (> (cdr z) (CDAR x)))) (CDR x))) 
                             (LIST (CAR x)) 
                             (qsorta (remove-if (FUNCTION (LAMBDA (z) (<= (cdr z) (CDAR x)))) (CDR x)))))))
==> qsorta
 
;; Проверим работу:
 
(qsorta (mkListL '(asd h dd w eeq sa sss dd d)))
 
==> ((d . 1) (w . 1) (h . 1) (dd . 2) (sa . 2) (dd . 2) (sss . 3) (eeq . 3) (asd . 3))
 
;; Сортирует верно...

(mapcar 'car '((d . 1) (w . 1) (h . 1) (dd . 2) (sa . 2) (dd . 2) (sss . 3) (eeq . 3) (asd . 3)))
 
==> (d w h dd sa dd sss eeq asd)

(defun task (lst) (mapcar 'car (qsorta (mkListL lst))))
 
==> task
 
(task '(qwe d f wwwwwww x cccccc))
 
==> (x f d qwe cccccc wwwwwww)

;; вспомогательная функция min2
 
(defun min2 (x y) (if (< x y) x y)) ;; если x < y вернет x, иначе y (минимум из двух чисел)
 
;; распространение min2 на произвольное к-во чисел
 
(defun min! (x) 
     (cond ((= (length x) 1) (car x))                 ;; если список сост. из одного числа, то мининум ему и равен
           ((= (length x) 2) (min2 (car x) (cadr x))) ;; если из двух - то вызываем min2
           (t (min2 (car x) (min! (cdr x))))))        ;; а иначе рекурсия - вызываем min2, примененный к 
                                                      ;; первому элементу и вызову min! на хвосте списка. 
 
;; Удаление из списка первого вхождения атома 
 
(defun remove (x a) 
     (cond ((null x) nil)                          ;; если список пуст - удалять нечего
           ((EQ a (car x)) (cdr x))                ;; если голова списка есть удаляемый атом - оставляем хвост
           (t (cons (car x) (remove (cdr x) a))))) ;; а иначе голову присоединяем к хвосту,
                                                   ;; из которого удален атом a 
  
;; Сортировка выбором
 
(defun sort (x) 
   (cond ((null x) nil)                                    ;; список пуст - сортировать нечего
         (t (cons (min! x) (sort (remove x (min! x) )))))) ;; иначе берем минмимум списка и 
                                                           ;; присоединяем его первым элементом к новому списку,
                                                           ;; который получается из сортировки исходного списка без первого минимума
 
(sort '(1 2 -3 33 12))
 
==> (-3 1 2 12 33)

(defun selection-sort (w)
  (when w (cons (mini w) (selection-sort (remove (mini w) w)))))
 
(defun mini (w)
  (mi (cdr w) (car w)))
 
(defun mi (w m)
  (cond ((null w) m)
    ((< (car w) m) (mi (cdr w) (car w)))
        ((mi (cdr w) m))))
 
> (selection-sort '(5 4 7 1 3))
(1 3 4 5 7)

(DEFUN remove (x L)
  (COND ((NULL L) NIL) 
        ((equal x (CAR L)) (remove x (CDR L)))
        (T (CONS (CAR L) (remove x (CDR L))))))