Навигация
Главная
Поиск
Форум
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
Содержание сайт... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Invision Power ... 65321
Организация зап... 63993
Модуль Forms 60879
Создание отчето... 60758
ТЕХНОЛОГИИ ДОСТ... 57086
Создание потоко... 56465
Пример работы с... 54337
Имитационное мо... 52534
Реклама
Сейчас на сайте
Гостей: 7
На сайте нет зарегистрированных пользователей

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

Лабораторная работа по динамическим спискам на Turbo Pascal (перемещение...
Моделирование работы ЭВМ на GPSS + Пояснительная записка
База данных склада на Delphi + Схема БД

Реклама



Подписывайся на 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 00:14:27 · 0 Комментариев · 12725 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
DragMe [Исходник ...
AID антивирус
БД сеть компьютер...
Обучение Borland ...
TMS
netBIOS
Tank [Исходник на...
Turbo Pascal for ...
C++ Builder: Книг...
PHP 5 в подлинник...
Язык программиров...
UmEdit
GPSS World Studen...
Цветной Grid
Файловый менеджер
Иллюстрированный ...
Изучаем Ассемблер
Pass [Исходник на...
ATComponents
около 291 статьи ...

Топ загрузок
Приложение Клие... 100376
Delphi 7 Enterp... 83135
Converter AMR<-... 20046
Borland C++Buil... 11186
GPSS World Stud... 10962
Borland Delphi ... 8131
Turbo Pascal fo... 6973
Visual Studio 2... 4964
Калькулятор [Ис... 4376
FreeSMS v1.3.1 3510
Случайные статьи
Контекстно-свободн...
Глава 18. Страт...
Найти переименован...
Недостатки рекурси...
Вывод элементарных...
Прямой метод решен...
X==Y
Очереди с приоритетом
Открытие существую...
Загрузка объекта W...
Моделирование расп...
Выравнивание загру...
7.2. Поиск в лаб...
Купить ноутбук
Команда DELETE
Web Proxy
Invalid symbol ref...
Ассоциативные масс...
Object type expected
Алгоритм unordered...
Новинка планшетов ...
Настройка параметр...
Анимационные прогр...
Описание перечисли...
Разрешение маршрут...
Статистика



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


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