Рекурсии в AutoLISP урок 10
Метод быстрой сортировки.
Немного справки:
Быстрая сортировка (англ. quicksort) - широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром.
Более подробно:
Quicksort
Быстрая_сортировка
Заключается алгоритм в разделении списка на две части по условию, что все элементы первого списка меньше, чем все элементы второго. На практике, берем первый элемент списка и сравниваем его со всеми остальными элементами. Все, что меньше, добавляем в список минимальных значений, остальные в список с максимальными значениями. Далее, рекурсивно применяем такую функцию к обоим спискам. Элемент считается стоящим на месте, если он один в списке. Объясню алгоритм подробнее на примере: eсть список '(2 3 1 0) и функция < Т.к. мы будем разделять список на подсписки, сначала его преобразуем во вложенный список '((2 3 1 0)). Далее берем для сравнения первый элемент первого подсписка и сравниваем его с каждым элементом первого подсписка без первого элемента, добавляя сравниваемый элемент в список минимальных значений, при условии, что сравниваемый элемент меньше тестового, иначе в список максимальных значений.
Получаем:
тестовое значение 2 минимальный список '(1 0) максимальный список '(3) потом объединяем все в один список '((1 0)(2)(3))
И начинаем все сначала... При таком подходе, может оказаться, что один из списков пустой, а значит на его месте появится пустой список — NIL. Для некоторого упрощения я добавил проверку списка на длину более двух элементов, если элементов всего два — их можно сразу поставить по местам. Этот алгоритм удобно реализовать логически поделив на три программы. Первая программа делит список на два, сравнивая все элементы с тестовым значением. Далее нам нужна программа, вызывающая сортировку и формирующая результирующий список. На входе в программу сортировки подается список, а мы собираемся делить его на подсписки, значит, для начала нужно создать список, в котором первым и единственным элементом, будет весь исходный список для сортировки, далее его будем делить на куски, внутри этого списка. Исходя из темы урока — изучение рекурсий, нужно максимально использовать рекурсии, но терять скорость выполнения не хотелось и я вынес создание вложенного списка из сортируемого, в отдельную программу.
(defun rec-quicksort-2 (lst lst1 lst2 test f) (cond ((not lst) (list lst1 (list test) lst2) ) (((eval f) (car lst) test) (rec-quicksort-2 (cdr lst) (cons (car lst) lst1) lst2 test f) ) (t (rec-quicksort-2 (cdr lst) lst1 (cons (car lst) lst2) test f)) ) ;_ cond ) ;_ defun (defun rec-quicksort-1 (lst f) (cond ((not lst) nil) ((not (car lst)) (rec-quicksort-1 (cdr lst) f)) ((not (cdar lst)) (cons (caar lst) (rec-quicksort-1 (cdr lst) f)) ) ((not (cddar lst)) (if (apply f (car lst)) (cons (caar lst) (cons (cadar lst) (rec-quicksort-1 (cdr lst) f))) (cons (cadar lst) (cons (caar lst) (rec-quicksort-1 (cdr lst) f))) ) ;_ if ) (t ((lambda (x) (rec-quicksort-1 (cons (car x) (cons (cadr x) (cons (caddr x) (cdr lst)))) f) ) ;_ lambda (rec-quicksort-2 (cdar lst) nil nil (caar lst) f) ) ) ) ;_ cond ) ;_ defun (defun rec-quicksort (lst f) ;(rec-quicksort '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) (function <)) (rec-quicksort-1 (list lst) f) ) ;_ defun ; Проверим: (setq lst '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) f (function <) ) ;_ setq (rec-quicksort lst f) ; Возвращает ; '(1 2 2 3 3 3 3 4 4 5 6 6 6 6 7 7 9)
Рассмотрим работу первой подпрограммы rec-quicksort-2 она имеет на входе:
lst — сортируемый список
lst1 — пустой список, будем наполнять его минимальными значениями
lst2 — пустой список, будем наполнять его максимальными значениями
test — тестовое значение, сравнивая с ним, будем решать, в какой из списков добавить элемент
F — тестовая функция
Алгоритм работы программы довольно прост — всего три проверки cond... В первой проверке — проверяем наличие списка — уточняем, что список не пустой. Если список закончился, значит нужно сформировать результирующий список:
'((минимальные значения) (тестовый элемент, относительно которого сортировали) (максимальные значения) )
Понятно, что списки максимальных и минимальных значений могут быть пустыми, а значит, мы будем использовать NIL. Вторая проверка — применение тестовой функции к первому элементу списка и тестовому элементу. Если первый элемент меньше тестового элемента, значит, первый элемент списка нужно добавить в список минимальных значений. Другими словами, вызываем рекурсивно программу с укороченным сортируемым списком, а в список минимальных элементов добавляем первый элемент списка. Третья проверка cond всегда верна — если программа до нее дошла, значит, у нас есть не пустой сортируемый список и первый элемент этого списка не меньше тестового значения. Значит, в этой ветке cond нужно добавить первый элемент списка в список максимальных значений и вызвать рекурсию с укороченным сортируемым списком.
(defun rec-quicksort-2 (lst lst1 lst2 test f) (cond ((not lst) ; Если кончился список (list ; Формируем список lst1 ; Список минимальных значений (list test) ; Список с тестовым значением lst2 ; Список максимальных значений ) ;_ list ) (((eval f) ; Активируем функцию (car lst) ; Первый элемент списка test ; Тестовое значение ) ; Если Т добавляем первый элемент в список минимальных значений (rec-quicksort-2 ; Самовызов рекурсии (cdr lst) ; Укороченный список (cons ; Формируем список (car lst) ; Первый элемент списка lst1 ; Список минимальных значений ) ;_ cons lst2 ; Список максимальных значений test ; Тестовое значение f ; Тестовая функция ) ;_ rec-quicksort-2 ) (t ; Если дошли, значит есть не пустой список ; и первое значение не меньше тестового значения (rec-quicksort-2 ; Самовызов рекурсии (cdr lst) ; Укороченный список lst1 ; Список минимальных значений (cons ; Формируем список (car lst) ; Первый элемент списка lst2 ; Список максимальных значений ) ;_ cons test ; Тестовое значение f ; Тестовая функция ) ;_ rec-quicksort-2 ) ;_ t ) ;_ cond ) ;_ defun ; Проверим: (setq lst '((7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1)) f (function <) ) ;_ setq (rec-quicksort-2 (cdar lst) nil nil (caar lst) f) ; Возвращает ; '((1 3 6 4 6 3 2 3 5 2 6 6 4 3) (7) (7 9))
Рассмотрим вторую рекурсивную подпрограмму — rec-quicksort-1 в ней будет пять проверок в cond. В первой проверке утверждаем, что сортируемый список не пустой, другими словами, что еще не весь список отсортирован. Во второй проверке смотрим что первый подсписок не пустой. Пустым он может оказаться, если в предыдущей программе у нас список минимальных или максимальных значений оказался пустым. В этом случае запускаем рекурсивно программу rec-quicksort-1 без первого подсписка. В третьей проверке смотрим что первый подсписок сортируемого списка, имеет не более одного элемента — если в подсписке один элемент, это значит элемент стоит на своем месте и его уже не надо сортировать относительно остальных элементов списка и мы можем его добавить в результирующий список. В четвертой проверке мы утверждаем, что первый подсписок имеет не более двух элементов. Если элементов всего два, значит, нет смысла вызывать сортирующую программу — их проще поставить на место сразу. Для начала применяем тестовую функцию к подсписку из двух элементов и формируем результирующий отсортированный список, добавляя к нему элементы из этого подсписка в порядке возрастания. В пятой проверке, если ее можно так назвать — никакой проверки нет — всегда T Понятно, что до этого места программа может дойти, только если есть сортируемый список, в котором первый подсписок имеет более двух элементов. Здесь мы первым делом сортируем первый подсписок на три подсписка. Используя, lambda функцию, временно запоминаем результат, и последовательно добавляем подсписки из полученного списка в сортируемый список без первого подсписка. Можно написать покороче.
Вместо:
((lambda (x) (rec-quicksort-1 (cons (car x) (cons (cadr x) (cons (caddr x) (cdr lst) ) ;_ cons ) ;_ cons ) ;_ cons f ) ;_ rec-quicksort-1 ) ;_ lambda (rec-quicksort-2 (cdar lst) nil nil (caar lst) f ) ;_ rec-quicksort-2 )
используя конструкцию:
(rec-quicksort-1 (apply (function append) (list (rec-quicksort-2 (cdar lst) nil nil (caar lst) f ) ;_ rec-quicksort-2 (cdr lst) ) ;_ list ) ;_ apply f ) ;_ rec-quicksort-1
Но эта конструкция работает несколько медленнее, чем предложенная выше...
Вот собственно и сама рекурсия:
(defun rec-quicksort-1 (lst f) (cond ((not lst) ; Если кончился список nil ; Заканчиваем рекурсию и возвращаем пустой список ) ((not (car lst)) (rec-quicksort-1 (cdr lst) f ) ;_ rec-quicksort-1 ) ((not (cdar lst)) ; Если в первом подсписке только один элемент (cons ; Формируем список (caar lst) ; Первый и единственный элемент первого подсписка (rec-quicksort-1 ; Самовызов рекурсии (cdr lst) ; Укороченный список f ; Тестовая функция ) ;_ rec-quicksort-1 ) ;_ cons ) ((not (cddar lst)) ; Если в первом подсписке только два элемента (if (apply ; Применяем функцию к списку f ; Тестовая функция (car lst) ; Первый подсписок ) ;_ apply (cons ; Формируем список (caar lst) ; Первый элемент первого подсписка (cons ; Формируем список (cadar lst) ; Второй элемент первого подсписка (rec-quicksort-1 ; Самовызов рекурсии (cdr lst) ; Укороченный список f ; Тестовая функция ) ;_ rec-quicksort-1 ) ;_ cons ) ;_ cons (cons ; Формируем список (cadar lst) ; Второй элемент первого подсписка (cons ; Формируем список (caar lst) ; Первый элемент первого подсписка (rec-quicksort-1 ; Самовызов рекурсии (cdr lst) ; Укороченный список f ; Тестовая функция ) ;_ rec-quicksort-1 ) ;_ cons ) ;_ cons ) ;_ if ) (t ; Если дошли, значит есть не пустой список ; и первый подсписок имеет более двух элементов ((lambda (x) ; Аргументом лямбда функции является результат программы rec-quicksort-2 (rec-quicksort-1 ; Самовызов рекурсии (cons ; Формируем список (car x) ; Список минимальных значений (cons ; Формируем список (cadr x) ; Список со средним элементом — один в списке (cons ; Формируем список (caddr x) ; Список максимальных значений (cdr lst) ; Сортируемый список без первого элемента ) ;_ cons ) ;_ cons ) ;_ cons f ; Тестовая функция ) ;_ rec-quicksort-1 ) ;_ lambda (rec-quicksort-2 ; Программа сортировки (cdar lst) ; Первый подсписок без первого элемента nil ; Пустой список минимальных элементов nil ; Пустой список максимальных элементов (caar lst) ; Первый элемент первого подсписка f ; Тестовая функция ) ;_ rec-quicksort-2 ) ) ;_ t ) ;_ cond ) ;_ defun ; Проверим: (setq lst '((7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1)) f (function <) ) ;_ setq (rec-quicksort-1 lst f) ; Возвращает ; '(1 2 2 3 3 3 3 4 4 5 6 6 6 6 7 7 9)
Последняя подпрограмма самая простая, можно сказать, что она вспомогательная, т.к. написана только для вызова функции сортировки с такими же аргументами, как у функции vl-sort. Ее задача, вложить сортируемый список в другой список и запустить программу сортировки.
(defun rec-quicksort (lst f) (rec-quicksort-1 (list lst) f) ) ;_ defun ; Проверим: (setq lst '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) f (function <) ) ;_ setq (rec-quicksort lst f) ; Возвращает ; '(1 2 2 3 3 3 3 4 4 5 6 6 6 6 7 7 9)
Старая версия сайта, доступна здесь.