Сортировка данных

 

Белорусский национальный технический университет

Факультет информационных технологий и робототехники

Кафедра ПОВТ и АС

 

 

 

 

 

 

 

 

 

 

 

Курсовой  проект

 

по дисциплине «Функциональное и логическое программирование»

на тему

«Сортировка данных»

 

 

 

 

 

 

 

 

 

 

Исполнитель:         студент ФИТР 3 курса гр. 107219

Сенькевич А.П.

 

Руководитель: доцент Ковальков А.Т.

 

 

 

 

МИНСК

2011

 

Белорусский национальный технический университет

Факультет информационных технологий и робототехники

Кафедра ПОВТ и АС

 

 

 

 

 

 

 

 

 

 

 

Пояснительная записка

К курсовому проекту

по дисциплине «Функциональное и логическое программирование»

на тему

«Сортировка данных»

 

 

 

 

 

 

 

 

 

 

Исполнитель: студент ФИТР 3 курса гр. 107219

Сенькевич А.П.

 

Руководитель: доцент Ковальков А.Т.

 

 

 

 

МИНСК

2011

 

 

Содержание

 

 

ВВЕДЕНИЕ…………………………………………………….………..5

1. ПОСТАНОВКА ЗАДАЧИ…………………………………..…...…...6

2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ…………………………………….……7

3. СТРУКТУРНАЯ СХЕМА ПРОГРАММЫ………………….………9

4. ОПИСАНИЕ ПРЕДИКАТОВ…………………….……...…….…...10

5. ТЕКСТ ПРОГРАММЫ………………………………………..…….12

6. ТЕСТИРОВАНИЕ ПРОГРАММЫ………………………….……...16

7. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ…………………………....………20

ВЫВОДЫ……………………………………………………………....21

ЛИТЕРАТУРА…………………………………………………….…...22

ПРИЛОЖЕНИЕ…………………………………….…...………….…………23

 

Введение

 

Курсовой проект “Сортировка данных” разработан на языке программирования ТурбоПролог, учитывая всю специфику данного языка, а особенно работа со списками и рекурсия.

Сила Турбо-Пролога заключается  в его возможностях поиска и сопоставления. Внутренние унификационные процедуры бесстрастно перебирают все возможные комбинации правил, пытаясь удовлетворить заданную программистом цель. Пролог,  как  видим,  базируется  на  естественных  для  человека логических  принципах,  и  поэтому, чем больше вы им занимаетесь, тем он становится все более привлекательным.

Турбо-Пролог является компиляторно-ориентированным  языком  программирования  высокого  уровня;  разработан  фирмой Borland  International  и  предназначен для программирования задач  из  области искусственного интеллекта. Как язык программирования ИИ Турбо-Пролог особенно хорош для создания экспертных систем, динамических баз данных, программ с  применением  естественно-языковых конструкций; он также может быть использован и для других задач общего характера.  Турбо-Пролог  имеет  окна,  цветную  графику и интерактивные средства ввода-вывода, что свидетельствует о его максимальном удобстве для пользователя прикладных программ.

Стоит отметить ещё одно свойство Пролога. Я бы назвал его языком сверхвысокого  уровня в том смысле, что он более  приближен к той предметной области, которой принадлежит решаемая задача, нежели традиционные языки высокого уровня. В связи с этим он удобен для создания пробных версий (или прототипов) программ с целью проверки работоспособности новых концепций и алгоритмов. И из-за этого же его свойства программы на Прологе зачастую выполняются медленнее, чем написанные "вручную" на традиционных языках. Объясняется это тем, что базовый алгоритм выполнения программы на Прологе основан на переборе большого числа вариантов решений.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Постановка задачи

 

Разработать программу сортировки данных:

• сортировка перестановкой;
• сортировка вставкой;
• быстрая сортировка;
• Сортировка слиянием.

Оценить алгоритмы по быстродействию.

 

Нужная операция выбирается из меню.

 

2. Теоретическая часть

 

Быстрая сортировка

 

Автором так  называемой "быстрой" сортировки является Хоар. Он назвал ее быстрой  потому, что в общем случае эффективность  этого алгоритма довольно высока. Идея метода следующая. Выбирается некоторый "барьерный" элемент, относительно которого мы разбиваем исходный список на два подсписка. В один мы помещаем элементы, меньшие барьерного элемента, во второй — большие либо равные. Каждый из этих списков мы сортируем тем же способом, после чего приписываем к списку тех элементов, которые меньше барьерного, вначале сам барьерный элемент, а затем — список элементов не меньших барьерного. В итоге получаем список, состоящий из элементов, стоящих в правильном порядке.

 

Предикат sort_q будет реализовывать алгоритм быстрой сортировки Хоара. Он будет состоять из двух предложений. Правило будет осуществлять с помощью предиката partition разделение непустого списка на два подсписка, затем сортировать каждый из этих подсписков рекурсивным вызовом себя самого, после чего, используя предикат conc (созданный нами ранее), конкретизирует второй аргумент списком, получаемым объединением отсортированного первого подсписка и списка, сконструированного из барьерного элемента (головы исходного списка) и отсортированного второго подсписка.

 

 

Сортировка вставкой

 

Сортировка вставкой основана на том, что если хвост списка уже отсортирован, то достаточно поставить первый элемент списка на его место в хвосте, и весь список будет отсортирован. При реализации этой идеи создадим два предиката.

 

Задача предиката insert — вставить значение (голову исходного списка) в уже отсортированный список (хвост исходного списка), так чтобы он остался упорядоченным. Его первым аргументом будет вставляемое значение, вторым — отсортированный список, третьим — список, полученный вставкой первого аргумента в нужное место второго аргумента так, чтобы не нарушить порядок.

 

Предикат sort_v, собственно, и будет организовывать сортировку исходного списка методом вставок. В качестве первого аргумента ему дают произвольный список, который нужно отсортировать. Вторым аргументом он возвращает список, состоящий из элементов исходного списка, стоящих в правильном порядке.

 

Пузырьковая сортировка

 

Идея этого метода заключается  в следующем. На каждом шаге сравниваются два соседних элемента списка. Если оказывается, что они стоят неправильно, то есть предыдущий элемент меньше следующего, то они меняются местами. Этот процесс продолжаем до тех пор, пока есть пары соседних элементов, расположенные в неправильном порядке. Это и будет означать, что список отсортирован.

 

Сортировка слияниям

 

Метод слияний — один из самых "древних" алгоритмов сортировки. Его придумал Джон фон Нейман еще в 1945 году. Идея этого метода заключается в следующем. Разобьем список, который нужно упорядочить, на два подсписка. Упорядочим каждый из них этим же методом, после чего сольем упорядоченные подсписки обратно в один общий список.

 

Для начала создадим предикат, который  будет делить исходный список на два. Он будет состоять из двух фактов и  правила. Первый факт будет утверждать, что пустой список можно разбить только на два пустых подсписка. Второй факт будет предлагать разбиение одноэлементного списка на тот же одноэлементный список и пустой список. Правило будет работать в случаях, не охваченных фактами, т.е. когда упорядочиваемый список содержит не менее двух элементов. В этой ситуации мы будем отправлять первый элемент списка в первый подсписок, второй элемент — во второй подсписок, и продолжать распределять элементы хвоста исходного списка.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Структурная схема  программы

Графический вид структурной схемы  программы находится в графическом приложении №1 на странице 21.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Описание предикатов

repeat – организация в программе цикла.

make_menu – создание меню и графического интерфейса.

process(Key)(char): (i) –создание системы запросов в меню.

 

begin_work – Главный предикат.

 

read_list (List)(string*): (o) – Чтение списка строк List.

 

write_list(List)(string*): (i) – Печать списка строк List.

 

sort_p (List1,List2,Num,Out)( string*, string*,integer,char): (i,o,o,i) – Сортировка списка строк перестановкой, где List1– входной список, List2 – полученный список при сортировке, Num – количество рекурсий, Out – показывает, нужно ли выводить промежуточные результаты сортировки или нет.

 

sort_v (List1,List2,Num,Out)( string*, string*,integer,char): (i,o,o,i) – Сортировка списка строк вставкой, где List1– входной список, List2 – полученный список при сортировке, Num – количество рекурсий, Out – показывает, нужно ли выводить промежуточные результаты сортировки или нет.

 

sort_q1 (List1,List2,Num,Out)( string*, string*,integer,char): (i,o,o,i) – Быстрая сортировка списка строк, где List1– входной список, List2 – полученный список при сортировке, Num – количество рекурсий, Out – показывает, нужно ли выводить промежуточные результаты сортировки или нет.

 

insert (El,List1,List2,Num)(string, string*, string*,integer): (i,i,o,o) – Вставка элемента El в список List1 и получаем список List2, где Num – подсчет количества рекурсий.

 

devide (Str,List1,List2,List3,Num)(string, string*, string*, string*,integer): (i,i,i,o,o) – Разбиение списка List1 на два списка List2 и List3, где Num – подсчет количества рекурсий.

 

сonnect (List1,List2,List3,Num)( string*, string*, string*,integer): (i,i,o,o)  – Соединение двух списков List1 и List2 в один List3, где Num – подсчет количества рекурсий.

 

q_sort (Sp,Sv,Sq,Res)(integer,integer,integer,string): (i,i,i,o) – поиск самой быстрой сортировки, где Sp,Sv,Sq – результаты работы каждой из сортировок, Res – самая быстрая сортировка.

 

fusion_sort(List1,List2,Num,Out)( string*, string*,integer,char): (i,o,o,i)- Сортировка списка строк слиянием, где List1– входной список, List2 – полученный список при сортировке, Num – количество рекурсий, Out – показывает, нужно ли выводить промежуточные результаты сортировки или нет.

 

splitting(List1,List2,List3,Num)( string*, string*, string*,integer): (i,i,o,o)- список List1 расщепляется на два подсписка List2 и List3, где Num – подсчет количества рекурсий.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Текст программы

 

DOMAINS

 

list_string=string*

 

file=myfile

 

PREDICATES

nondeterm repeat

nondeterm begin_work

nondeterm make_menu

nondeterm process(char)

nondeterm read_list(list_string)

nondeterm write_list(list_string)

nondeterm sort_p(list_string,list_string,integer,char)

nondeterm perest(list_string,list_string,integer)

nondeterm sort_v(list_string,list_string,integer,char)

nondeterm insert(string,list_string,list_string,integer)

nondeterm sort_q1(list_string,list_string,integer,char)

nondeterm devide(string,list_string,list_string,list_string,integer)

nondeterm connect(list_string,list_string,list_string,integer)

nondeterm q_sort(integer,integer,integer,integer,string)

nondeterm write_s(list_string,char)

nondeterm sort_view(list_string,list_string,char)

nondeterm fusion_sort(list_string,list_string,integer,char)

nondeterm fusion(list_string,list_string,list_string,integer)

nondeterm splitting(list_string,list_string,list_string,integer)

 

CLAUSES

 

begin_work:-

  make_menu.

 

 

 make_menu:-

  repeat,

  write(" Выберите один из пунктов меню, нажав на клавиши от 1 до 5 ."),nl,

  write(" 1. Сортировка перестановкой."),nl,

  write(" 2. Сортировка вставкой."),nl,

  write(" 3. Быстрая сортировка."),nl,

  write(" 4. Сортировка слиянием."),nl,

write(" 5. Оценка алгоритмов на быстродействие."),nl,

  write("   Esc - Выход из программы."),nl,

  readchar(C),

  process(C),

  C=27,!.

 

 process('1'):-

  write(" 1. Сортировка перестановкой."),nl,

  write(" Введите список, для окончания ввода нажмите Esc:"),nl,

  read_list(List1),

  sort_p(List1,List2,_,'n'),

  write(" Полученный результат: "),nl,

  write_list(List2),write("Нажмите любую клавишу..."),nl,

readchar(_),!.

 

process('2'):-

  write(" 2. Сортировка вставкой."),nl,

  write(" Введите список, для окончания ввода нажмите Esc:"),nl,

  read_list(List1),

  sort_v(List1,List2,_,'n'),

  write(" Полученный результат: "),nl,

  write_list(List2),write("Нажмите любую клавишу..."),nl,

  readchar(_),!.

 

process('3'):-

  write(" 3. Быстрая сортировка. "),nl,

  write(" Введите список, для окончания ввода нажмите Esc:"),nl,

  read_list(List1),

  sort_q1(List1,List2,_,'n'),

  write(" Полученный результат: "),nl,

  write_list(List2),write("Нажмите любую клавишу..."),nl,

  readchar(_),!.

  process('4'):-

  write(" 4. Сортировка слиянием. "),nl,

  write(" Введите список, для окончания ввода нажмите Esc:"),nl,

  read_list(List1),

  fusion_sort(List1,List2,_,'n'),

  write(" Полученный результат: "),nl,

  write_list(List2),write("Нажмите любую клавишу..."),nl,

  readchar(_),!.

 

 

process('5'):-

write(" 5. Оценка алгоритмов на быстродействие."),nl,

write(" Оценка сортировки проводится по количеству рекурсий,"),nl,

write("  осуществляемых  при сортировке списка элементов."),nl,

write(" Введите список, для окончания ввода нажмите  Esc:"),nl,

read_list(List),

sort_p(List,_,Np,'n'),

sort_v(List,_,Nv,'n'),

sort_q1(List,_,Nq,'n'),