> 1 <

Автор Сообщение

mnevseravno

Members


Статус

1 сообщений

Где: Russia
Род занятий:
Возраст:

#5943   2012-04-06 21:16 GMT+3 часа(ов)      
необходимо написать быструю сортировку на лиспе. нашла код в интернете, но не очень его понимаю, кто нибудь объясните пожалуйста
(defun quicksort (lis) (if (null lis) nil
(let* ((x (car lis)) (r (cdr lis)) (fn (lambda (a) (< a x))))
(append (quicksort (remove-if-not fn r)) (list x)
(quicksort (remove-if fn r))))))

megamanx

Members


Статус

307 сообщений

Где: Russia
Род занятий:
Возраст:

#5949   2012-04-08 19:28 GMT+3 часа(ов)      
(defun quicksort (lis)
;;функция quicksort, принимает список в качестве аргумента
(if (null lis) nil
;;если список пуст, то возвратим nil, который "закроет" возвращаемый список
(let*
;;создадим локальные переменные
((x (car lis))
;;первый элемент списка будет за x
(r (cdr lis))
;;все остальные элементы списка за r
(fn (lambda (a) (< a x))))
;;fn - это анонимная функция, которая проводит сравнение переданного ей аргумента
;;a с заданой нами локальной переменной x
(append
;;составляем список из того, что возвратит функция quicksort
;;когда ей в качестве аргумента передаётся список r, из которого удалены все
;;элементы, не удовлетворяющие функции fn...
(quicksort (remove-if-not fn r)) (list x)
;;... и из того, что вернёт эта функция от списка r, из которого
;;удалены все элементы, удовлетворяющие функции fn.
(quicksort (remove-if fn r))))))
;;исследуем
(trace quicksort)
(quicksort '(6 5 3 4 2 1))
0: (QUICKSORT (6 5 3 4 2 1))
1: (QUICKSORT (5 3 4 2 1))
2: (QUICKSORT (3 4 2 1))
3: (QUICKSORT (2 1))
4: (QUICKSORT (1))
5: (QUICKSORT NIL)
5: QUICKSORT returned NIL
5: (QUICKSORT NIL)
5: QUICKSORT returned NIL
4: QUICKSORT returned (1)
4: (QUICKSORT NIL)
4: QUICKSORT returned NIL
3: QUICKSORT returned (1 2)
3: (QUICKSORT (4))
4: (QUICKSORT NIL)
4: QUICKSORT returned NIL
4: (QUICKSORT NIL)
4: QUICKSORT returned NIL
3: QUICKSORT returned (4)
2: QUICKSORT returned (1 2 3 4)
2: (QUICKSORT NIL)
2: QUICKSORT returned NIL
1: QUICKSORT returned (1 2 3 4 5)
1: (QUICKSORT NIL)
1: QUICKSORT returned NIL
0: QUICKSORT returned (1 2 3 4 5 6)
(1 2 3 4 5 6)
 

Гугл выдаёт другой алгоритм, который ИМХО, лучше
(defun q-sort (l &optional (f #'<))
(if (null (cdr l)) l
(append (q-sort (remove-if-not #'(lambda (x) (funcall f x (car l))) (cdr l)) f)
(list (car l))
(q-sort (remove-if #'(lambda (x) (funcall f x (car l))) (cdr l)) f))))
I wish I'd made you angry earlier
> 1 <


Онлайн :

0 пользователь(ей), 38 гость(ей) :




Реклама на сайте: