Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 63909
Модуль Forms 63636
ТЕХНОЛОГИИ ДОСТ... 60481
Пример работы с... 59876
Имитационное мо... 55958
Реклама
Сейчас на сайте
Гостей: 20
На сайте нет зарегистрированных пользователей

Пользователей: 13,079
новичок: Openair
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Движение шарика в эллиптическои параболоиде на Delphi [OpenGL] + Блок схемы
Обработка задач на ЭВМ на GPSS + Пояснительная записка
База данных - рабочее место кассира на Delphi + бд Access

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
7.7. Сортировка

Иногда полезно упорядочить список элементов в соответствии с заданным порядком их следования. Если элементами списка являются целые числа, то для того чтобы определить соблюден ли порядок следования, можно использовать предикат '‹'. Список (1, 2, 3) упорядочен, поскольку любая пара соседних целых чисел этого списка удовлетворяет предикату '‹'. Если элементами списка являются атомы, то мы можем воспользоваться предикатом меньше, о чем уже говорилось в гл. 3. Список [alpha,beta,gamma] упорядочен в алфавитном порядке, поскольку каждая пара соседних атомов этого списка удовлетворяет предикату меньше.
Специалисты по информатике разработали много методов сортировки списков, когда задан некоторый предикат, который говорит нам о том, находятся ли соседние элементы списка в требуемом порядке следования. Мы рассмотрим Пролог-программы для четырех таких методов: наивная сортировка, сортировка включением (вставками), сортировка методом пузырька и быстрая сортировка. В каждой программе используется предикат упорядочено, который может быть определен через '‹' меньше или любой другой предикат по вашему усмотрению, в зависимости от того, какого рода структуры вы сортируете. При этом предполагается, что целевое утверждение упорядочено(Х, Y) доказуемо, если объекты X и Y удовлетворяют требуемому порядку следования, т. е. если X в некотором смысле меньше чем Y .
Один из способов сортировки чисел в порядке возрастания состоит в следующем: вначале создается некоторая перестановка чисел, затем проверяется расположен ли полученный список в порядке возрастания. Если это не так, то создается новая перестановка чисел. Этот метод известен под названием наивная сортировка:
наивсорт(L1,L2):- перестановка(L1,L2),отсортировано(L2),!.
перестановка(L,[H|T]):-присоединить(V,[Н|U],L), присоединить(V,U,W), перестановка(W,Т).
перестановка([],[]).
отсортировано(L):- отсортировано(0,L).
отсортировано(_,[]).
отсортировано(N,[H|T]):- упорядочено(N,Н),отсортировано(Н,T).



Используемый здесь предикат присоединить многократна определялся ранее. В этой программе предикаты имеют следующий смысл:
Наивсорт(L1, L2) означает, что L2 – это список, являющийся упорядоченной версией списка L1;
Перестановка(L1, L2) означает, что L2 - это список, содержащий все элементы списка L1 в одном из многих возможных порядков их следования; в терминологии разд. 4.3 – это генератор.
Предикат отсортировано(L) означает, что числа в списке L упорядочены в порядке возрастания; это – 'контролер'.
Процесс поиска упорядоченной версии списка заключается в создании некоторой перестановки элементов и проверки ее упорядоченности. Если это так, то единственный ответ найден. Иначе мы вынуждены продолжать создание перестановок. Это не очень эффективный метод сортировки списка.
При сортировке включением каждый элемент списка рассматривается отдельно и включается в новый список на соответствующее место. Этот метод используется, например, при игре в карты, когда игрок сортирует имеющиеся на руках карты, вынимая и переставляя по одной карте за раз. Целевое утверждение вклюсорт(X, Y) доказуемо тогда, когда список Y является упорядоченной версией списка X . Каждый элемент удаляется из головы списка и передается предикату вклюсорт2 , который включает этот элемент в список и возвращает измененный список.
вклюсорт([],[]).
вклюсорт([Х|L],М):- вклюсорт(L,N), вклюсорт2(Х,N,М).
вклюсорт2(Х,[А|L],[А|М]):- упорядочено(А,Х),!,вклюсорт2(Х,L,М).
вклюсорт2(Х,L,[Х |L]).



Чтобы сделать предикат сортировки включением более универсальным, удобно задавать предикат проверки порядка следования в качестве аргумента предиката вклюсорт. Используем для этого предикат ' =..', который рассматривался в гл. 6:
вклюсорт([],[],_).
вклюсорт([Х|L],М,О):- вклюсорт(L,N,О),вклюсорт2(Х,N,М,О).
вклюсорт2(Х,[А|L],[А|М],0):-Р=..[O,А,Х], call(P),! , вклюсорт2(Х,L,М,O).
вклюсорт2(Х,L,[Х|L],О).



Теперь мы можем использовать такие цели как вклюсорт(А,В,'‹') и вклюсорт(А,В,меньше), т. е. отпадает необходимость в предикате упорядочено. Этот метод может быть распространен.и на другие алгоритмы сортировки данного раздела.
При сортировке методом пузырька в списке ищется пара соседних элементов, расположенных не по порядку следования. Если такие элементы находятся, то они меняются местами. Этот процесс продолжается до тех пор, пока перестановки станут ненужными. Если при сортировке включением выбранный элемент как бы «тонет», попадая на нужное место, то сортировка методом пузырька названа так потому, что здесь элементы, подобно пузырькам воздуха, постепенно «всплывают», занимая соответствующее место.
пусорт(L,S):-присоединить(Х,[А,В|Y],L),упорядочено(В,А),присоединить(Х, [В, А|Y],M),пусорт(M,S).
пусорт(L,L).
присоединить([],L,L).
присоединить([Н|Т],L[Н|V]):- присоединить(Т,L,V).



Заметим, что здесь применяется тот же самый предикат присоединить , с которым мы встречались ранее. Этот пример отличается от предыдущих необходимостью возвратного хода после каждого найденного решения. Поэтому в первом правиле в определении пусорт «отсечение» не используется. Эта программа еще один пример «недетерминированного» программирования,- для выбора элементов списка L здесь используется предикат присоединить . При этом контроль полноты выполненных перестановок целиком возложен на присоединить .
Быстрая сортировка - это более сложный метод сортировки, предложенный Хоором и применимый для сортировки больших списков. Для реализации быстрой сортировки на Прологе мы должны сначала разделить список, состоящий из головы Н и хвоста Т , на два списка L и М такие, что:
• все элементы L меньше или равны Н ;
• все элементы М больше чем Н ;
• порядок следования элементов в L и М такой же как в [Н |Т] .
После того, как мы разделили список, применяем быструю сортировку к каждому из полученных списков (это рекурсивная часть), и присоединяем М к L Цель разбить(H,T,L,M) разделяет список [Н |Т] на списки L и М , как сказано выше:
paзбить(H,[A|X],[A|Y],Z):- А=‹ Н, разбить(Н,Х,Y,Z).
разбить(Н,[А|Х],Y,[А|Z]):- А › Н, разбить(Н,Х,Y,Z).
разбить(_,[], [],[]).



Тогда программа быстрой сортировки примет вид:
бысорт([],[]).
бысорт([H|T],S):-разбить(Н,Т,А,В),бысорт(А,А1),бысорт(В,В1), присоединить(А1, [H|B1],S).



Предикат присоединить можно встроить внутрь программы сортировки. Тогда получается другой предикат
бысорт2 ([H|T], S,X):-разбить(Н,T,А,В), бысорт2(А,S,[Н|Y]), бысорт2(B,Y,X).
бысорт2([],Х,Х).



В этом случае третий аргумент используется как временная рабочая область, и при обращениях к бысорт2 этот аргумент должен заполняться пустым списком.
Более подробные сведения о методах сортировки можно найти в книге D. Knuth, The Art of Computer Programming, v. 3 (Sort and Searching), Addison-Wesley, 1973 (Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3 (Сортировка и поиск). М.: Мир, 1978.- Перев.) Метод быстрой сортировки Хоора описан в его статье в Computer Journal n. 5 (1962), стр. 10-15.
Упражнение 7.5. Проверьте, что предикат перестановка (L1, L2) строит все перестановки заданного списка L1 (причем каждую по одному разу) и выдает их как альтернативные значения списка L2 . В каком порядке строятся эти решения?
Упражнение 7.6. Быстрая сортировка лучше всего работает ка больших списках, поскольку там она обеспечивает более быструю сходимость к решению. В то же время объем работы, выполняемой на каждом уровне рекурсии быстрой сортировки, превышает то, что делается в других методах, из-за использования разбить. Поэтому, при сортировке небольших списков рекурсивные вызовы бысорт, видимо, можно заменить обращениями к другим методам сортировки, например, к сортировке включением. Разработайте «гибридную» программу, которая использует быструю сортировку для обработки больших подсписков (списков, полученных с помощью предиката разбить), но переключается на другой метод (сортировка включением) при значительном уменьшении длины подсписка. Подсказка: поскольку разбить должен просмотреть все элементы списка, то он может заодно подсчитать и длину списка.
Опубликовал Kest July 10 2009 01:14:27 · 0 Комментариев · 13143 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
IconCut [Исходник...
iComm v.6.1 - выв...
Пример создания W...
Применение фильтр...
KOL & MCK v1.69
DirHTMLReportBuil...
Borland C++Builde...
DCAVI
RAS
RbControls
Искусство програм...
Halcyon
Turbo Pascal for ...
ZipTV
Игра в крестики н...
Ранги для форума
CLR via C#
Программирование ...
Иллюстрированный ...
Архив значков

Топ загрузок
Приложение Клие... 100449
Delphi 7 Enterp... 85821
Converter AMR<-... 20067
GPSS World Stud... 12518
Borland C++Buil... 11576
Borland Delphi ... 8504
Turbo Pascal fo... 7023
Visual Studio 2... 4989
Калькулятор [Ис... 4739
FreeSMS v1.3.1 3536
Случайные статьи
Выбор наилучших ал...
Требования делегир...
Осуществление запи...
Unknown Identifier
Университет
Разберем детали. П...
Использование фоно...
Пошаговое выполнен...
Спам поисковых машин
Именование объектов
показана куча из 1...
Формирование масси...
Пассивные интерфей...
Что делает команда...
AVL дерево
Invalid variable r...
Linux — система бе...
fail
Адаптер для указат...
Основы службы подд...
Чего мы хотим от п...
Идентификаторы в я...
Управление риском
Текстовое наполнен...
Объяснение решения
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?