Методы сортировки

       ФГБОУ ВПО «Сыктывкарский государственный  университет»

       Институт  точных наук и информационных технологий

       Кафедра информационной безопасности 
 

       Допустить к защите

       Зав. кафедрой, к.ф.-м.н., доцент

       __________Л.С.  Носов

       «___»_______2012г. 

       Курсовая  работа по дисциплине

       «Методы программирования и прикладные алгоритмы» 

       Методы  сортировки. 
 
 

       Научный руководитель:

       к.ф.-м.н., доцент                                                  _____ Ю.В. Гольчевский   

                                                                                                                    «___»_______2012г. 

        

       Исполнитель:

       студент группы 123                                          ________ Б. А. Нестеров

        

       «___»_______2012г. 
 

Сыктывкар, 2012

СОДЕРЖАНИЕ

Введение  ………...…………...…………………………………………………..………………3

Глава 1. Алгоритмы сортировок

      1.1 Сортировка методом обмена.……………………………………………..…………… 5

      1.2 Сортировка с помощью выбора…………………………………………………………6

      1.3 Сортировка методом Хоара ………………………………………...…………………. 7

      1.4 Сортировка методом Уильямса-Флойда……...………………………………………..9

Глава 2. Эффективность методов

     2.1 Сравнение методов сортировки………………………………………………………..12

     2.2 Применение методов……………………………………………………………………14

Глава 3.  Графический интерфейс

3.1 Стартовое окно………………………………………………………………………… 15

3.2 Построение неотсортированных прямоугольников.………………..………………… 15

3.3 Сортировка отсортированных прямоугольников…………………………………… 16

Заключение  …………………....………………………………………………………………. 17

Библиографический список …………………………………………………...………….….. 18

Приложения…...………………………………………………………………………………...19 
 
 
 
 

ВВЕДЕНИЕ

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

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

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

    Цель  моей работы: оценить эффективность методов сортировки обменами, вставками, метода Хоара и метода Уильмса-Флойда.

    Для достижения поставленной цели необходимо решить следующие задачи:

1. Изучить алгоритмы сортировки обменами, сортировки вставками(Пузырьком),   сортировки методом Хоара(Быстрая) и метода  Уильямса-Флойда(Пирамидальная).
2. Реализовать и наглядно продемонстрировать  эти методы в следующей задаче:

 

1. Сгенерировать N пар точек (x₁, y₁) и (x₂, y₂) случайным образом.
2. Вычислить площади прямоугольников, построенных по этим парам точек. Пронумеровать эти прямоугольники.
3. Отсортировать эти прямоугольники по возрастанию площади. Использовать сортировку обменами, вставками, метод Хоара, метод Уильямса-Флойда.
4. Оценить эффективность этих методов для большого количества элементов, измерив время работы.
5. *Построить прямоугольники, закрашенные разным цветом.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ГЛАВА 1. Алгоритмы сортировок

1. Сортировка методом обмена

 

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

   Мы  повторяем проходы по массиву, сдвигая  каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы  можно интерпретировать как пузырьки в чане с водой, причём вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу(см. табл. 1). Такой метод широко известен под именем «пузырьковая сортировка». В своем простейшем виде он представлен в программе  1.

Таблица 1.

   Пример  пузырьковой сортировки 

 
 

   Программа 1. Процедура ExchangeSort 

   procedure ExchangeSort( var A : mas );

   var

     x : integer;

   begin

     for i := N downto 2 do

     for j := 2 to i do

     if A[j] < A[j - 1] then

     begin

          x := A[j];

          A[j] := A[j - 1];

          A[j - 1] := x;

     end;

   end; 

 1.2 Сортировка с помощью выбора 

Этот  прием основан на следующих принципах:

1. Выбираем элемент с наименьшим ключом.
2. Передвигаем на 1 позицию направо элементы, больше выбранного элемента.
3. Вставляем выбранный элемент в нужную позицию.
4. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один , самый большой элемент.

Процесс работы этого метода приведен в таблице 2. Реализация этого алгоритма в программе 2. 

  Таблица 2.

Пример  сортировки вставками 

 

    Программа 2. Процедура InsertSort 

    procedure InsertSort( var A : mas );

    var

      i, k : Integer;

      x : integer;

    begin

      for i := 2 to N do

      begin

           k := i;

           x := A[i];

          while (A[k - 1] > x) do

            begin

                 A[k] := A[k - 1];

                 k := k - 1;

            end;

                    A[k] := x;

      end;

     end; 

3. Сортировка методом Хоара

  Ч. Хоар изобрел алгоритм сортировки массива  и назвал его метод быстрой  сортировки(Quicksort).

  В Quicksort исходят из того соображения, что для достижения наилучшей Эффективности сначала лучше производить перестановки  на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но из этого примера можно извлечь нечто действительно поучительное.

  Давайте, попытаемся воспользоваться таким  алгоритмом: выберем наугад какой-либо элемент(назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент >x, затем будем просматривать массив справа, пока не встретим <x. Теперь поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массив. В результате массив окажется разбитым на левую часть, с ключами меньше(или равными)  x, и правую – с ключами больше(или равными)  x. Теперь этот процесс представим в виде процедуры  в программе 3.

  Программа 3. Функция Partition

  function Partition( var A : mas; l, r : Integer; x : integer ) : Integer;

    var

    i, j : Integer;

    t : integer;

  begin

    i := l - 1;

    j := r + 1;