Метод быстрой сортировки (quick_sort)

Идея: 1 Удалить из списка L какой-либо элемент X и разбить оставшуюся часть на два списка- Smaller и Larger

2 разбиение(деление) списка производить следующим образом: все элементы>X принадлежат списку Larger,остальные- списку Smaller

3 Отсортировать список Smaller и результат – список Sort_Smaller

4 Отсортировать список Larger и результат – список Sort_larger

5 Получить результирующий упорядоченный список как конкатенацию списков Sort_Smaller и [X|Sort_Larger].

[5,2,4,8,9,3,7] --исходный список

/ --удаляем X=5(обычно голова списка)

[2,4,8,9,3,7]

/ \ --деление списка по признаку-<=5 >5

[2,4,3] [8,9,7]

/ \ ---сортировка

[2,3,4] [7,8,9]

\ / ---конкатенация с добавлением X

[2,3,4,5,7,8,9] ---отсортированный список

Время выполнения сортировки зависит от того, насколько повезет при разбиении сортируемого списка. Если оба разбиваемых списка примерно одинаковой длины, то время выполнения порядка n*log n,где n-длина исходного списка

Если один из списков значительно длиннее другого, то время выполнения порядка n² (как и при сортировке со вставками- с ростом n время растет пропорционально n².)

Анализ показывает, что чаще произведенная сортировка оказывается ближе к лучшему случаю.

Листинг 6.3.3. быстрая сортировка

trace

domains

number=integer

list=number*+

predicates

quick_sort(list,list)

split(list,number,list,list)

append(list,list,list)

clauses

quick_sort([],[]).

quick_sort([X|Tail],Sort_list):-

split(Tail,X,Little_list,Large_list),

quick_sort(Little_list,Sort_little_list),

quick_sort(Large_list,Sort_large_list),

append(Sort_little_list,[X|Sort_large_list],Sort_list).

split([],_,[],[]).

split([X|Tail],Y,[X|Sort_little_list],Sort_large_list):-

X<=Y,

split(Tail,Y,Sort_little_list,Sort_large_list).

split([X|Tail],Y,Sort_little_list,[X|Sort_large_list]):-

X>Y,

split(Tail,Y,Sort_little_list,Sort_large_list).

append([],L,L).

append([X|L1],L2,[X|L3]):-

append(L1,L2,L3).

Список литературы

1. Адаменко А, Кучумов А. Логическое программирование и Visual prolog: руководство в подлиннике – СПб.: БХВ-Петербург,2003 -993с.

2.Стерлинг Л.,Шапиро Э. Искусство программирования на языке Пролог:Пер с анг.-М.:Мир,1990. -235с.

3.Братко И. Алгоритмы искусственного интеллекта на языке Prolog,3-е издание.:пер. с англ. – М.:Издательский дом “Вильямс”, 2004. – 640с.

4.Хювёнен Э.,Сеппянен Й. Мир Лиспа.В 2-х т. Т1:Введение в язык Лисп и функциональное программирование. Пер. с финск. – М.: Мир, 1990. -447c.

5.Душкин Р.В.Функциональное программирование на языке Haskell.-М.:ДМК Пресс,2007. -608с.