Я очень долго не врубался в алгоритм быстрой сортировки. Фактически, до сегодняшнего дня. С утра несколько раз пробовал написать на Лиспе в таком варианте, в каком он здесь на Си, но не получалось нифига, постоянно либо не полностью сортировался, либо индекс за границы последовательности вылетал(в лиспе нет цикла for в таком виде, в каком он есть в паскале и Си-подобных языках, пришлось и это велосипедить). Вот. Но потом я заглянул на английскую страницу, увидел там псеводкод:
function quicksort(array) var list less, greater if length(array) ≤ 1 return array select a pivot value pivot from array for each x in array if x < pivot then append x to less if x > pivot then append x to greater return concatenate(quicksort(less), pivot, quicksort(greater)) |
схему:
И внезапно просветлел.
(defun qsort (array sort-function) (if (<= (length array) 1) array (let ((pivot (elt array (round (/ (length array) 2)))) less greater pivots) (map nil (lambda (x) (cond ((equalp x pivot) (push x pivots)) ((funcall sort-function x pivot) (push x less)) ((not (funcall sort-function x pivot)) (push x greater)))) array) (concatenate (typecase array (string 'string) (vector 'vector) (list 'list)) (qsort less sort-function) pivots (qsort greater sort-function)))))
Моя функция принимает последовательность, функцию - реляционный оператор, выбирает pivot как элемент из середины и с помощью map(когда тип возвращаемой последовательности указывается nil, эта функция не возвращает ничего и используется просто для побочных эффектов), используя переданный реляционный оператор, раскидывает элементы по спискам - в less, greater или в pivots соответственно. Потом она создает новый массив из less, pivots и greater списков, предварительно рекурсивно вызывая себя для сортировки less и greater. Не совсем корректо, правда, работает с функциями вроде =, string= итд - просто как попало перемешивает массив. Но, во-первых, кому придет в голову сортировать оператором равенства, и во-вторых, это можно поправить, например, поставив в if наверху вместо (<= (length array) 1) что-нибудь типо (or (<= (length array) 1) (member sort-function (list #'= #'string= #'string-equal #'char= #'char-equal #'eq #'eql #'equal #'equalp)))
Работает вобщем так: (qsort #(1 9 8 7 3 5 0 2 4 6) #'<) вернет #(0 1 2 3 4 5 6 7 8 9)
(qsort "ХУИТА" #'char<) соответственно "АИТУХ" UPD: Внезапно. (defun prob-qsort (array rel-operator) (if (<= (length array) 1) array (let ((pivot (elt array (random (length array))))) (concatenate (typecase array (string 'string) (bit-vector 'bit-vector) (vector 'vector) (list 'list)) (prob-qsort (remove-if #'(lambda (x) (or (equalp x pivot) (not (funcall rel-operator x pivot)))) array) rel-operator) (remove-if-not #'(lambda (x) (equalp x pivot)) array) (prob-qsort (remove-if #'(lambda (x) (or (equalp x pivot) (funcall rel-operator x pivot))) array) rel-operator))))) |