Не пишем quicksort на Common Lisp
Потому что незачем. Во-первых, все уже написано и не раз. Во-вторых, штатный sort в общем случае работает не хуже. В-третьих, в моду входят задачки, требующие не столько умения пользоваться сортировкой, сколько обходиться вообще без нее. Взять, к примеру, вот эту с собеседования в Microsoft.1. Анаграммы Имеется массив человеческих слов. Некоторые слова могут являться анаграммами по отношению друг у другу. Надо найти количество таких слов, причем сложность алгоритма должна быть линейной. Очевидное решение — отсортировать сами слова, потом отсортировать массив, пройтись по нему и посчитать количество слов с самоподобными соседями. На CL это можно написать так:(defvar *words* (list «thore» «ganamar» «notanagram» «anagram» «other»))
((lambda (words) (loop for (a b c) in (mapcar #'list words (append '(») words) (append '(» ») words)) count (or (equal a b) (equal b c)))) (sort (mapcar (lambda (one-word) (sort one-word #'char-lessp)) *words*) #'string-lessp)) Читать дальше →
