Реализация алгоритмов сортировки данных средствами функционального программирования

Размещено на http://www.allbest.ru

АКАДЕМИЯ МАРКЕТИНГА И СОЦИАЛЬНО-ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ - ИМСИТ (г. Краснодар)

Факультет информатики и ВТ

Кафедра математики и вычислительной техники

КУРСОВАЯ РАБОТА

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

на тему: "Реализация алгоритмов сортировки данных средствами функционального программирования"

Краснодар 2014

Реферат

Курсовая работа 12 страниц, 2 листингов, , 6 источников.

Данные, сортировка, алгоритм, функциональное программирование, f#, реализация

Объектом исследования является мультипарадигмальный язык программирования F#.

Цель работы состоит в приобретении навыков по работе с языком программирования F#, осознании его синтаксиса и особенностей, а так же применение языка F# в решении задач сортировки массивов данных различными способами .

программирование хоар алгоритм

Содержание

Введение

1. Обоснование выбора языка программирования

2. Изучение предметной области

3. Практическая реализация алгоритма сортировки данных

3.1 Быстрая сортировка (сортировка Хоара)

3.2 Реализация на процедурном языке программирования

3.3 Реализация на функциональном языке программирования

Заключение

Список использованных источников и литературы

Введение

Функциональное и логическое программирование - это две различные парадигмы программирования, которые, однако, имеют много общего: они представляют декларативное программирование. В декларативных языках, в отличие от императивных (процедурных или объектно-ориентированных), описывается не алгоритм решения задачи, а знания об объектах и процессах соответствующей предметной области. Алгоритм же вырабатывается и реализуется в ходе логического вывода с помощью специального механизма.

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

Наибольшую популярность сейчас имеет язык F#, - современный аналог языков Лисп и Пролог, ставший доступным в большей степени после релиза MS Visual Studio 2010.

1. Обоснование выбора языка программирования

Не так давно было объявлено, что в составе стандартной поставки Visual Studio 2010 появится, помимо Visual Basic и C#, ещё один язык программирования: F#.

F# -это также и объектно-ориентированный язык, прекрасно интегрирующийся с платформой .NET, и в некоторой степени императивный. Можно рассматривать F# как полноценное пришествие функционального программирования на платформу .NET (в смысле его индустриальной доступности), а можно и как еще один .NET-язык с множеством “причуд” и с непривычным, но очень компактным синтаксисом.

Если же начать рассматривать F# с другой стороны, не вдаваясь в его функциональную сущность, то можно заметить, что это компактный язык, в котором есть в т.ч. автоматический вывод типов (нам почти никогда не приходится описывать типы данных для объектов) при статической типизации, в результате чего получается код, как на динамическом языке, но с проверкой типов и более эффективным порождаемым байт-кодом.

Майкрософт в реализации Visual Studio позиционирует F# как язык, удобный для решения различных задач обработки данных. В то же время не предполагается (хотя это и возможно), что F# будет широко использоваться для построения пользовательских интерфейсов, поэтому поддержки F# со стороны визуальных дизайнеров не обещается.

Всё вышесказанное вызывает значительный интерес к языку F# со стороны студентов, преподавателей и академического сообщества в целом.

2. Изучение предметной области

Прежде всего давайте разберемся с определением.

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

Итак, каждый алгоритм сортировки состоит из трех основных частей:

Функция сравнения пары элементов сортируемого массива

Процедура перестановки, меняющая местами пару элементов

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

В данной работе будет рассмотрена реализация метода сортировки Хоара.

3. Практическая реализация алгоритма сортировки данных

3.1 Быстрая сортировка (сортировка Хоара)

Шаги алгоритма быстрой сортировки таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный -- справа от него. Обычный алгоритм операции:

- Два индекса -- l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.

- Вычисляется индекс опорного элемента m.

- Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.

- Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

- Если r = l -- найдена середина массива -- операция разделения закончена, оба индекса указывают на опорный элемент.

- Если l < r -- найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.

3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

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

3.2 Реализация на процедурном языке программирования

В качестве примера реализации указанного алгоритма был выбран язык Паскаль, так как он наиболее прост в понимании и более показателен в исполнении.

procedure qSort(var ar: array of real);

procedure sort(var ar: array of real; low, high: integer);

var i, j: integer;

m, wsp: real;

begin

i:=low; j:=high; m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента

repeat

while ar[i]<m do Inc(i); // изменить порядок сортировки можно

while ar[j]>m do Dec(j); // поменяв >< в этих двух строках

if i<=j then begin

wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp;

Inc(i); Dec(j);

end;

until i>j;

if low<j then sort(ar, low, j);

if i<high then sort(ar, i, high);

end;

begin

sort(ar, 0, High(ar));

end;

Листинг 1 Реализация сортировки методом Хоара на Паскале

3.3 Реализация на функциональном языке программирования

На функциональном языке программирования F# сортировка будет выглядеть значительно более компактно:

let rec quicksort = function

[ ] -> [ ]

| h::t -> quicksort ([ for x in t when x<=h -> x])

@ [h] @ quicksort ([ for x in t when x>h -> x]);;

Листинг 2 Реализация сортировки методом Хоара на языке F#

Итак, мы видим, что F# довольно приятен, плюс ко всему, разница в реализации между Листингом 1 и Листингом 2 наглядно показывает нам, что функциональное программирование - это принципиально иная область, разительно отличающаяся от привычных нам традиционных языков, типа C#.

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

Заключение

В процессе написания данной курсовой работы по предмету «Функциональное и логическое программирование» мной был более подробно изучен язык программирования F#.

Помимо того, был подробно рассмотрен алгоритм сортировки методом Хоара и его реализация на двух различных языках программирования.

Список использованных источников и литературы

1. Сергиевский Г. М. Функциональное и логическое программирование : [учеб. пособие] / Г. М. Сергиевский, Н. Г. Волченков. ЁC М. : Академия, 2010.

2. Томпсон С. Программирование в Erlang / C. Томпсон, Ф. Чезарини. М.: ДМК Пресс, 2012.

3. Сошников Д. Функциональное программирование на F# / Д. Сошников. М.: ДМК Пресс, 2012.

4. Lisper.ru [Электронный ресурс]. ЁC Электрон. дан. ЁC lisper.ru, cop. 2009-2010. ЁC Режим доступа : http://lisper.ru

5. Цуканова Н.И. Логическое программирование на языке Visual Prolog: [учеб. пособие] / Н. И. Цуканова, Т. А. Дмитриева. М.: Горячая Линия - Телеком, 2008

6. Ездаков А. М. Функциональное и логическое программирование : [учебно-методическое пособие] / К. С. Дмитренко, А. М. Ездаков. М.: Бином. Лаборатория знаний, 2011.

7. Лесовская И. Н. Функциональное и логическое программирование : [учеб. пособие] / И. Н. Лесовская, М. В. Курак. М.: Издательский дом ВВИА им. проф. Н.Е.Жуковского, 2009

8. Смит К. Программирование на F#: [учеб. пособие] / К. Смит, А. С. Киселев. М. : Символ-Плюс, 2014.

9. Кубенский А.А. Функциональное программирование : [учеб. пособие] / Г. М. Нефедов, А. А. Кубенский. СПб. : СПбГУ ИТМО.

10. Шалимов П.Ю. Функциональное программирование : [учеб. пособие] / Г. М.: Издательский дом ВВИА им. проф. Н.Е.Жуковского, 2011

Размещено на Allbest.ru