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

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

Курсовая работа

Разработка проекта на С++ «Сортировка линейного массива методом сортировки слиянием (Merge sort) и анализ его трудоемкости»

Введение

В настоящее время вычислительная техника проникла практически во все сферы человеческой деятельности. С помощью ЭВМ можно решать самые разные задачи. Но для того, чтобы решить поставленную задачу, необходимо указать последовательность действий, выполнение которых приведёт к требуемому результату, - составить программу. Для удобства работы с ЭВМ эта операция производится с помощью языков программирования (высокого или низкого уровня).

Один из широко используемых языков программирования - это Visual C++, который можно использовать для написания программ, работающих в операционной среде Windows. На данное время одной из самых распространенных его версий является Microsoft Visual C++, и среда программирования Microsoft Developer Studio 6.0.

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

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

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

1. Основные теоретические аспекты алгоритма и сортировки

1.1 Понятие алгоритма и сортировки

Слово «Алгоритм» происходит от algorithmi - латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело - реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершать исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.

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

Цель сортировки - облегчить поиск элементов в отсортированном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонной книге, в оглавлениях, в библиотеках, в словарях, да почти всюду. Даже маленьких детей приучают привадить вещи «в порядок», и они сталкиваются с некоторым видом сортировки за долго до того, как узнают что-либо об арифметике. Зависимость выбора алгоритмов от структуры данных - явление довольно частое, особенно при обработке данных, и в случае сортировки она настолько сильна, что методы сортировки подразделяют на два вида: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах.

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

1.2 Основные способы и алгоритмы сортировки массивов

На данный момент существует множество способов сортировки линейных массивов, расскажу о нескольких методах сортировки.

1. Метод «пузырька»

Самым простым методом сортировки является так называемый метод «пузырька». Чтобы уяснить его идею, представьте, что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход «снизу», берется первый элемент и поочередно сравнивается с последующими. При этом:

§ если встречается более «легкий» (с меньшим значением) элемент, то они меняются местами;

§ при встрече с более «тяжелым» элементом, последний становится «эталоном» для сравнения, и все следующие сравниваются с ним.

В результате наибольший элемент оказывается в самом верху массива.

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

2. Сортировка посредством выбора

Принцип метода:

Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

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

В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве «основы» и затем весь массив разбивается на две части. Одну часть составляют все элементы, равные или большие «основы», а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован.

4. Пирамидальная сортировка

Пирамидальная сортировка в некотором роде является модификацией такого подхода, как сортировка выбором, с тем лишь отличием, что минимальный (или максимальный) элемент из неотсортированной последовательности выбирается за меньшее количество операций. Для такого быстрого выбора из этой неотсортированной последовательности строится некоторая структура. Именно суть данного метода и состоит в построении такой структуры, которая называется пирамидой.

5. Метод Шелла

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

6. Метод Слияния.

Сортировка слиянием - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определённом порядке. Эта сортировка - хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Более подробно этот метод будет раскрыт в следующей главе.

2. Реализация алгоритма сортировки массива методом слияния

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

Алгоритм сортировки слиянием был предложен праотцом современных компьютеров - Джоном фон Нейманом. Сам метод является устойчивым, т.е. он не меняет одинаковые по значению элементы в списке. Как уже было сказано, сортировка массива методом слияния - В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так:

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

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

3.в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.

Пример сортировки слиянием.

Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.

Для решения задачи сортировки эти три этапа выглядят так:

1. Сортируемый массив разбивается на две части примерно одинакового размера;

2. Каждая из получившихся частей сортируется отдельно, например - тем же самым алгоритмом;

3. Два упорядоченных массива половинного размера соединяются в один.

Пример работы алгоритма на массиве 3, 7, 8, 2, 4, 6, 15:

Слияние имеет большое практическое применение. Например, у Вас есть 2 списка

a [l+step]=tmp[step];

номеров телефонов, отсортированных по возрастанию и их нужно объединить в один список, тоже отсортированный по возрастанию. Перейдем непосредственно к самому алгоритму. Представим, что мы имеем 2 массива M, N, содержащие упорядоченные элементы. Нужно выполнить слияние этих массивов с массивов P. Для этого: вначале сравнивается элемент M[1] с элементом N[1] и меньший из низ записывается в P[1]. Если M[1] меньше N[1], то при выполнении следующего шага сравниваться уже будут M[2] и N[1], если наоборот - сравнивать будем M[1] и N[2]. И так до тех пор, пока один из начальных массивов не опустошится. Тогда оставшиеся элементы в другом массиве дописываются в массив P.

Попробуем алгоритм в действии. Пусть массив M содержит 3,5,8,11,16, а массив N содержит 1,5,7,9,12,13,18,20. Смотрим на схему:

Этот алгоритм работает обычно медленней, чем быстрая сортировка, однако у него есть ряд преимуществ: во первых он показывает стабильные результаты при сортировке определённого количества данных, в то время как при быстрой сортировке эти результаты могут довольно сильно различаться. Во-вторых, при большом количестве повторяющихся элементов программа не уходит в глубокую рекурсию. Главный недостаток - использование дополнительной памяти.

Существует несколько вариантов сортировки слиянием:

1. Двухпутевое слияние

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

2. Нисходящая сортировка слиянием

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

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

3. Восходящая сортировка слиянием

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

Порядок выполнения слияний определяется рекурсивной структурой алгоритма. Однако подфайлы обрабатываются независимо и слияния могут выполнятся в различных.

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

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

1. Седжвик Р. Фундаментальные алгоритмы на С++.DiaSoft.2001

2. Шилдт Г. Полный справочник по С++. Вильямс.2006

3. http://algolist.manual.ru/sort/merge_sort.php

4. http://www.delphiplus.org/fundamentalnie-algoritmy-i-struktury-dannih/sortirovka-sliyaniem.html

5. http://algolist.manual.ru/sort/merge_sort.php

6. http://iproc.ru/parallel-programming/lection-6/

7. Н. Вирт «Алгоритмы + структуры данных = программы» (1985)

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