На этом шаге мы рассмотрим несколько алгоритмов внутренней сортировки.
1. Начнем изложение с описания простого предиката для проверки упорядоченности элементов в числовом списке.
Пример 1.
(DEFUN TESTP (LAMBDA (LST) ; Предикат для проверки упорядоченности по возрастанию ; ; элементов в числовом списке ; (COND ( (NULL LST) T ) ( (COND ( (EQ (LENGTH LST) 1) T ) ( (COND ( (> (CAR LST) (CADR LST)) NIL ) ( T (TESTP (CDR LST)) )) )) ) ) ))
2. Описание же некоторых алгоритмов внутренней сортировки мы начнем с сортировки внутренним слиянием. Основой процесса слияния является фундаментальная идея упорядочения данных путем чередования элементов из двух и более упорядоченных списков.
Пример 2. Функция, "сливающая" элементы двух (двухпоточное слияние) числовых списков X и Y, элементы которых отсортированы по возрастанию, в "упорядоченный" по возрастанию список.
(DEFUN SORTING1 (LAMBDA (X Y)
(COND ( (NULL X) Y )
( T (INSERT1 (CAR X) (SORTING1 (CDR X) Y)) )
)
))
; ------------------------ ;
(DEFUN INSERT1 (LAMBDA (A L)
(COND ( (NULL L) (LIST A) )
( (< A (CAR L)) (CONS A L) )
( T (CONS (CAR L) (INSERT1 A (CDR L))) )
)
))
Тестовый пример:
$ (SORTING1 '(1 3 5 7) '(4 6 8)) (1 3 4 5 6 7 8)
3. Сортировка обменом - это общий термин, используемый для описания семейства минимальных по памяти методов сортировки, которые меняют местами элементы списка, если предшествующий элемент "больше" предыдущего. Парный обмен, стандартный обмен и просеивание являются тремя простыми формами сортировки обменом [1, с.24].
Пример 3. Сортировка элементов числового списка по возрастанию методом стандартного обмена (называемый также "методом пузырька").
(DEFUN PRIMER (LAMBDA (LST)
(COND ( (UPORIAD LST) LST )
( T (PRIMER (SORTIROVKA LST)) )
)
))
; -----------------------------
(DEFUN SORTIROVKA (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( (COND ( (EQ (LENGTH LST) 1) LST )
( (COND ( (> (CAR LST) (CADR LST))
(CONS (CADR LST)
(SORTIROVKA
(CONS (CAR LST )
(CDDR LST))))
)
( T (CONS (CAR LST)
(SORTIROVKA
(CDR LST))) )) )) )
)
))
; --------------------------
(DEFUN UPORIAD (LAMBDA (LST)
(COND ( (NULL LST) T )
( (COND ( (EQ (LENGTH LST) 1) T )
( (COND ( (> (CAR LST) (CADR LST)) NIL )
( T (UPORIAD (CDR LST)) )
)
)
)
)
)
))
4. Сортировка вставками есть общее название группы методов сортировки, основанных на последовательной вставке "новых" элементов в увеличивающийся упорядоченный список. Среди них есть три существенно разных метода: линейная вставка, центрированная вставка и двоичная вставка [1, с.33]. Эти методы сортировки различаются методами поиска подходящего места для вставки элемента.
Простейшим методом является линейная вставка. Как следует из названия, в этом методе уже существующий список рассматривается как простой линейный список, просматриваемый поэлементно сверху вниз, пока не будет найдена соответствующая позиция для нового элемента.
Этот метод обычно используется тогда, когда процесс, внешний к данной сортировке, динамически вносит добавления в список, все элементы которого известны и который должен все время поддерживаться в упорядоченном состоянии. Сортировка выполняется каждый раз при получении нового элемента, размещая этот элемент в нужное место списка и облегчая контроль.
Пример 4.
(DEFUN SORTING (LAMBDA (L) ; Сортировка неупорядоченного списка L ; ; методом линейной вставки ; (COND ( (NULL L) NIL ) ( T (INSERT (CAR L) (SORTING (CDR L))) ) ) )) ; ----------------------- ; (DEFUN INSERT (LAMBDA (A L) ; Функция INSERT добавляет элемент A в упорядоченный ; ; список L так, чтобы сохранилась упорядоченность ; (COND ( (NULL L) (LIST A) ) ( (< A (CAR L)) (CONS A L) ) ( T (CONS (CAR L) (INSERT A (CDR L))) ) ) )) ; -------------------------- ; (DEFUN RASSTAV (LAMBDA (NEW L) ; Функция RASSTAV позволяет элементы списка NEW ; ; вставить в упорядоченный список L ; (COND ( (NULL NEW) L ) ( T (INSERT (CAR NEW) (RASSTAV (CDR NEW) L)) ) ) ))
Тестовый пример:
$ (SORTING '(5 4 3 2 1 6)) (1 2 3 4 5 6) $ (RASSTAV '(4 3 1) '(1 2 5 6)) (1 1 2 3 4 5 6)
Пример 5.
(DEFUN SORTING (LAMBDA (L RANG) ; Сортировка неупорядоченного списка L. ; ; RANG - список, задающий правило упорядочения ; ; Функции SORTING, INSERT и LESS-Р образуют ; ; трехуровневую вложенную рекурсивную структуру ; (COND ( (NULL L) NIL ) ( T (INSERT (CAR L) (SORTING (CDR L) RANG) RANG) ) ) )) ; ---------------------------- ; (DEFUN INSERT (LAMBDA (A L RANG) ; Функция INSERT добавляет элемент A в упорядоченный ; ; список L так, чтобы сохранилась упорядоченность, если ; ; порядок любых двух элементов задается предикатом ; ; LESS-P. RANG - список, задающий правило упорядочения ; ; Функции INSERT и LESS-Р образуют двухуровневую вло- ; ; женную итеративную структуру ; (COND ( (NULL L) (LIST A) ) ( (LESS-P A (CAR L) RANG) (CONS A L) ) ( T (CONS (CAR L) (INSERT A (CDR L) RANG)) ) ) )) ; ------------------------------- ; (DEFUN RASSTAV (LAMBDA (NEW L RANG) ; Функция RASSTAV позволяет элементы списка NEW ; ; вставить в упорядоченный список L. ; ; RANG - список, задающий правило упорядочения ; (COND ( (NULL NEW) L ) ( T (INSERT (CAR NEW) (RASSTAV (CDR NEW) L RANG) RANG) ) ) )) ; ---------------------------- ; (DEFUN LESS-P (LAMBDA (A B RANG) ; Предикат LESS-P проверяет, находится ли элемент ; ; A ранее элемента B в соответствии с определенным ; ; порядком следования элементов в списке RANG ; (COND ( (NULL RANG) NIL ) ( (EQ A (CAR RANG)) T ) ; А раньше ; ( (EQ B (CAR RANG)) NIL ) ; B раньше ; ( T (LESS-P A B (CDR RANG)) ) ) ))
Тестовые примеры:
$ (SORTING '(B A C) '(A B C D E)) (A B C) $ (INSERT 6 '(5 7 8) '(1 2 3 4 5 6 7 8 9)) (5 6 7 8) $ (RASSTAV '(B C) '(A B D) '(A B C D E)) (A B B C D) $ (LESS-Р B E '(A B C D E)) T $ (LESS-Р E B '(A B C D E)) NIL
Пример 6.
(DEFUN RANK (LAMBDA (X Y) ; Функция RANK упорядочивает список, заданный в ; ; качестве ее первого аргумента, переставляя его ; ; элементы в той последовательности, в какой они ; ; встречаются в списке, являющемся значением вто- ; ; рого аргумента ; (COND ( (NULL X) NIL ) ( T (CONS (FIRST X Y) (RANK (REMOVEF (FIRST X Y) X) Y)) ) ) )) ; ---------------------- ; (DEFUN FIRST (LAMBDA (X Y) ; Функция FIRST среди элементов списка, заданного в ; ; качестве значения первого аргумента, выбирает тот, ; ; который раньше встречается в списке, заданном в ; ; качестве значения второго аргумента. Если ни один ; ; из элементов первого списка не содержится во вто- ; ; ром, то выбирается первый элемент первого списка. ; (COND ( (NULL Y) (CAR X) ) ( (MEMBER (CAR Y) X) (CAR Y) ) ( T (FIRST X (CDR Y)) ) ) )) ; -------------------------- ; (DEFUN REMOVEF (LAMBDA (X LST) ; Функция REMOVEF удаляет из списка LST первое вхож- ; ; дение элемента X на самом верхнем уровне ; (COND ( (NULL LST) NIL ) ( (EQUAL X (CAR LST)) (CDR LST) ) ( T (CONS (CAR LST) (REMOVEF X (CDR LST))) ) ) ))
(1) Лоpин Г. Соpтиpовка и системы соpтиpовки. - М.: Hаука, 1983. - 384 с.
На следующем шага мы рассмотрим дополнительные функции сортировки в muLISP85.
