Сортировка вставками - Lisp

Узнай цену своей работы

Формулировка задачи:

1) реализовать сортировку списка вставками. 2)описать функцию и сделать проверку чтобы при вводе например n=1 вышел верный расчёт..

Решение задачи: «Сортировка вставками»

textual
Листинг программы
(defun ins (a lst)
  (let ((r nil) (flg t))
    (dolist (i lst t)
      (when (and flg (> i a)) (push a r) (setq flg nil))
      (push i r))
    (when flg (push a r))
    (reverse r)))
 
 
(defun i-sort (lst)
  (let ((r (list (car lst))))
    (dolist (i (cdr lst) r)
      (setq r (ins i r)))))
 
==> I-SORT
 
(i-sort '(1 2 3 1 2 3 1 2 3 -1 6 -9))
 
==> (-9 -1 1 1 1 2 2 2 3 3 3 6)

Объяснение кода листинга программы

Код реализует функцию сортировки вставками, которая называется i-sort. Она принимает на вход список, который необходимо отсортировать. Сначала определяется вспомогательная функция ins, которая сортирует список вставками. Она принимает два аргумента: элемент, который необходимо вставить в список, и сам список. В функции ins используется цикл dolist, который проходит по элементам списка. Если текущий элемент больше элемента a и флаг flg не равен nil, то элемент a вставляется в начало списка, а флаг сбрасывается в nil. Если флаг равен nil, то текущий элемент просто добавляется в конец списка. После завершения цикла dolist, если флаг flg не равен nil, то элемент a добавляется в конец списка. В конце функции ins, список переворачивается с помощью функции reverse. Функция i-sort определяет список r, который инициализируется первым элементом из входного списка. Затем в цикле dolist проходят по остальным элементам списка. Для каждого элемента i выполняется функция ins, которая сортирует список r вставками. Результат функции ins присваивается переменной r. В конце функции i-sort, отсортированный список r возвращается в качестве результата. Пример использования функции i-sort: (i-sort '(1 2 3 1 2 3 1 2 3 -1 6 -9)) Результат выполнения: (-9 -1 1 1 1 2 2 2 3 3 3 6)

Оцени полезность:

12   голосов , оценка 4.083 из 5