Быстрая сортировка на LISP

[Sparky]

Добрый день, у меня на учебе начался лисп, необходимо реализовать быструю сортировку, нашла кучу алгоритмов, но не могу их понять, может кто-то сталкивался с подобной задачей и сможешь объяснить что и как нужно сделать? могу выложить примеры прог найденвх мной, чтоб объяснили по ним

[Utkin]

Сообщение от Sparky

Добрый день, у меня на учебе начался лисп, необходимо реализовать быструю сортировку, нашла кучу алгоритмов, но не могу их понять, может кто-то сталкивался с подобной задачей и сможешь объяснить что и как нужно сделать? могу выложить примеры прог найденвх мной, чтоб объяснили по ним

Выложите, авось вместе чего и выйдет .

ЗЫ. А на каком факультете на шепелявых (одно из значений lisp - шепелявость) учат ?

[Sparky]

1.

 (DEFUN FIRST_EL(n lst)
 (COND (( < = n 0) NIL)
       ((NULL lst) NIL)
       (1 (CONS (CAR lst) (FIRST_EL (- n '1) (CDR LST))))
 )
)

(DEFUN LAST_EL(n lst)
 (COND ((<= n 0) LST)
       ((NULL lst) NIL)
       (1 (LAST_EL (- n '1) (CDR LST)))
 )
)

(DEFUN SPLIT(lst)
 (SET 'fi (FIRST_EL (/ (LENGTH lst) 2) lst))
 (SET 'li (LAST_EL  (LENGTH fi) lst))
 (LIST fi li)
)

(DEFUN MERGE(lst1 lst2)
 (COND ((NULL lst1) lst2)
       ((NULL lst2) lst1)
       ((> (CAR lst1) (CAR lst2)) (CONS (CAR lst2) (MERGE lst1 (CDR lst2))))
       (1 (CONS (CAR lst1) (MERGE (CDR lst1) lst2)))
 )
)

(DEFUN SORT(LST)
 (COND ( (eq (LENGTH (CAR (SPLIT LST))) 1) (MERGE (CAR (SPLIT LST)) (CAR(CDR (SPLIT LST)))))
       ( 1 (MERGE (SORT (CAR (SPLIT LST))) (SORT(CAR (CDR (SPLIT LST))))))
 )
)

2.

(defun my-qsort (list-for-sort sort-fun-less sort-fun-more)
  (if (not list-for-sort) nil
      (append (my-qsort (remove (first list-for-sort) 
                                (rest list-for-sort) 
                                :test sort-fun-less) 
                        sort-fun-less 
                        sort-fun-more)
              (list (first list-for-sort))
              (my-qsort (remove (first list-for-sort) 
                                (rest list-for-sort) 
                                :test sort-fun-more) 
                        sort-fun-less 
                        sort-fun-more))))

;; пару примеров использования

CL-USER> (my-qsort '(3 1 6 3 1 34) #'< #'>=)
(1 1 3 3 6 34)

Факультет механико-математический, предмет называется языки программирования

[Utkin]

(defun my-qsort (list-for-sort sort-fun-less sort-fun-more)
  (if (not list-for-sort) nil
      (append (my-qsort (remove (first list-for-sort) 
                                (rest list-for-sort) 
                                :test sort-fun-less) 
                        sort-fun-less 
                        sort-fun-more)
              (list (first list-for-sort))
              (my-qsort (remove (first list-for-sort) 
                                (rest list-for-sort) 
                                :test sort-fun-more) 
                        sort-fun-less 
                        sort-fun-more))))

(defun my-qsort (list-for-sort sort-fun-less sort-fun-more)
определим функцию my-sort
list-for-sort - список элементов для сортировки

(if (not list-for-sort) nil
Если список для сортировки не содержит элементы вернем Nil

На большее меня не хватило .
Однако видны рекурсионные вызовы самой себя с перестановкой первого элемента.
list - это создание списка.

Касательно первого случая, то там, ИМХО разбираться проще - составные элементы функции вынесены как самостоятельные - получение первого, последнего элементов, слияние.
COND это вторая форма условия (почти как if).