На этом шаге мы приведем несколько функций из muLISP85, которые можно использовать при сортировке.

    В версии muLISP85 есть две функции-модификаторы, предназначенные для выполнения сортировки элементов списков: SORT и MERGE.

    Синтаксис функции SORT:

    (SORT LIST TEST)

    Если TEST является вариантом перестановки двух аргументов, то функция SORT сортирует элементы списка LIST на основе теста TEST и возвращает результат.

    Тест (TEST Object1 Object2) возвращает NIL тогда и только тогда, когда Object1 располагается "после" Object2 или равен ему. Кроме того, сортировка является верной и в том случае, когда элементы списка LIST, которые функция TEST находит равными, будут стоять в том же порядке в результате.

    Функция SORT выполняет сортировку и обьединение, при этом количество требуемого времени пропорционально log₂n, где n - это длина списка LIST. Например:

   $ (SORT '(5 2 7 3 -4) '<)
   (-4 2 3 5 7)
   $ (SORT '(DOG COW CAT) 'STRING<)
   (CAT COW DOG)

    Код функции SORT имеет вид:

   (DEGUN SORT (LST TST)
      ( (NULL LST) NIL )
      ( (NULL (CDR LST)) LST )
      ( (SETQ LST (CONS (SORT (SPLIT LST) TST)
                        (SORT LST TST)))
        (MERGE (CDR LST) (CAR LST) TST)
   )

    Синтаксис функции MERGE:

    (MERGE LIST1 LIST2 TEST)

    Если тест TEST является вариантом перестановки двух аргументов, то функция MERGE объединяет элементы списка LIST1 и списка LIST2 на основе теста TEST и возвращает результат.

    Функция (TEST Object1 Object2) возвращает NIL тогда и только тогда, когда Object1 располагается после Object2 или равен ему. Обьединение является верным в том случае, когда если элемент списка LIST1 равен элементу списка LIST2, то элемент списка LIST1 будет стоять перед элементом списка LIST2 в результате. Например:

   $ (MERGE '(2 4 6 8 10) '(3 5 7 11) '<)
   (2 3 4 5 6 7 8 10 11)

    Приведем код функции:

   (DEFUN NERGE (LST1 LST2 TST)
      ( (ATON LST1) LST2 )
      ( (ATOM LST2) LST1)
      ( (FUNCALL TST (CAR LST2) (CAR LST1))
           (RPLACD LST2 (MERGE LST1 (CDR LST2) TST)) )
      (RPLACD LST1 (MERGE (CDR LST1) LST2 TST))
   )

    Для оценки времени сортировки Вы можете воспользоваться в версии muLISP83 и более старших функцией TIME, синтаксис которой

    (TIME FL)

    Функция TIME возвращает количество пройденного времени с тех пор, как были установлены системные часы, с точностью до сотых долей секунды. Если флаг FL не равен NIL, то функция устанавливает часы в 0.

    Функция может использоваться для определения наиболее эффективного алгоритма решения определенной задачи. Сброс часов до 0 не влияет на счетчик времени в операционной системе, а только на внутренний счетчик времени muLISP. Например:

   $ (TIME T) (RECLAIM) (TIME)
   50

    На следующем шаге мы познакомимся с организацией поиска в списках.

Предыдущий шаг Содержание Следующий шаг