Notice: Undefined index: moes_p in /home/elpanov/elpanov.com/docs/index.php(3) : eval()'d code on line 1
ElpanovEvgeniy | Рекурсии, урок 10

Новая версия сайта, доступна здесь.




Рекурсии, урок 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)