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

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

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

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

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

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

       __________Л.С.  Носов

       «___»_______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;

    repeat

     repeat

      j := j - 1;

     until x >= A[j];

     repeat

      i := i + 1;

     until A[i] >= x;

     if i < j then

     begin

      t := A[i];

      A[i] := A[j];

      A[j] := t;

     end;

    until i >= j;

    Partition := j;

 end;

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

  Программа 4. Процедура RecoursiveQuicksort

    procedure RecoursiveQuick( var A : mas; l, r : Integer );

    var

    m : Integer;

   begin

    if l < r then

    begin

     m := Partition(A, l, r, A[(l + r) div 2]);

     RecoursiveQuick(A, l, m);

     RecoursiveQuick(A, m + 1, r);

    end;

  end; 
 

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

 

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

  Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется  к виду "пирамиды". На втором этапе осуществляется сортировка "пирамиды".  

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

  X[1]

  X[2] X[3]

  X[4] X[5] X[6 ] X[7]

  X[8] X[9] ................................ 
 

  Структура дерева имеет логический характер - в памяти компьютера все элементы массива всеравно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка X[2i] и X[2i+1], где i - индекс данного элемента. Элементы массива, являющегося "пирамидой", обладают дополнительными свойствами:  

  1. Любой элемент пирамиды X[i] не  меньше, чем его элементы-потомки  X[2i] и X[2i+1] (соответственно первый  элемент обладает максимальным  значением):  

  X[i] >= X[2i],

  X[i] >= X[2i+1]  

  2. Любая подпоследовательность элементов вида X[n\2+1], X[n\2+2], ... X[n] также является пирамидой, обладающей свойствами 1 и 2. После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.  

  В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и "укоротим" массив на 1 элемент с "хвост а". Наибольший элемент массива окажется последним. "Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент X[1] и его потомки - X[2] и X[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент X[1] и наибольший из потомков: max(X[2], X[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор, пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом. Реализация этого алгоритма в программе 5. 

  Программа 5. Процедура PiramidaSort 

  Procedure PiramidaSort(var A: mas);

  Var t, k, i, Y: Integer;

  Begin

     For i := 2 to N do { создание структуры бинарного дерева-"пирамиды" }

     begin

        t := i;

          while t <> 1 do

          begin k := t div 2;

                 If A[k] >= A[t] then t := 1

                 else

                 begin

                    Y:=A[k]; A[k]:=A[t]; A[t]:=Y;

                    t := k;

                 end

          end

     end;

     For i := N-1 downto 1 do { сортировка массива-"пирамиды" }

     begin

        Y:=A[i+1]; A[i+1]:=A[1]; A[1]:=Y;

        t := 1;

        While t <> 0 do

        begin

           k := t+t;

           If k > i then t := 0

           else

           begin

              If k < i then If A[k+1] > A[k] then k := k+1;

              If A[t] >= A[k] then t := 0

              else

              begin

                 Y:=A[k]; A[k]:=A[t]; A[t]:=Y;

                 t := k

              end;

           end;

        end;

     end;

  End; 
 

ГЛАВА 2. Эффективность  методов

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

  Чтобы оценить время работы алгоритмов использовалась программа, которая  формировала массив случайных целых чисел на отрезке [0,50000] целых чисел, а затем сортировала этот массив каждым из алгоритмов сортировки. Были получены результаты для массивов с количеством элементов от 1000 до 20000 с интервалом 1000. В таблице 3 представлены усредненные результаты, полученные в ходе их проведения.

  Таблица 3.

  Время сортировки

 

  Проанализировав полученные результаты, можно сделать  несколько выводов. Несложно заметить, что наилучшую скорость работы показал алгоритм сортировки Хоара. Так же хорошую скорость показал метод сортировки Уильямса-Флойда. Когда количество элементов массива не превышало 50 000, упорядочивание происходило практически мгновенно, остальные алгоритмы показали не высокую скорость работы и применение их при разработке серьезных программ не допустимо.

   Методы сортировки Уильямса-Флойда и Хоара это в своём роде улучшение алгоритмов выбора и обмена.  Поэтому сравним их попарно.

На  рисунке 1 представлен график зависимости  времени работы от количества элементов  методов обмена и выбора.

  

  Рисунок 1. График зависимости времени работы от количества элементов методов  обмена и выбора( синяя- метод обмена, красная - метод выбора).

    Из рисунка 1 видно, что метод сортировки выбором работает быстрее для большого количества элементов.

  На  рисунке 2 представлен график зависимости  времени работы от количества элементов методов Хоара и Уильямса-Флойда. Алгоритм Хоара или как его ещё называют алгоритм быстрой сортировки показал более высокую скорость и признан лучшим алгоритмов сортировки массивов из представленых.

  

  Рисунок 2. График зависимости времени работы от количества элементов методов Хоара и Уильямса-Флойда(синий-Уильямса-Флойда, красный- Хоара).

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

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

  Метод сортировки Хоара достаточно трудно реализовать. Он работает по принципу рулетки и зависит от выбора граничного элемента. При неудачном выборе граничного числа он работает медленно. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ГЛАВА 3. Графический интерфейс

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

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

 

Рисунок 3. Стартовое окно 

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

Если после  генерирования нажать кнопку построить,  то прямоугольники нарисуются в неотсортированном порядке (рис.4).

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

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

Если мы отсортировали  прямоугольники по площадям  любым  из представленных методов,  то после нажатия кнопки построить программа построит их в порядке возрастания (рис.5).

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

ЗАКЛЮЧЕНИЕ.

В ходе курсовой работы были выполнены следующие  задачи.

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     БИБЛИОГРАФИЧЕСКИЙ СПИСОК.

1. Н. Вирт Алгоритмы и структуры данных. – М.: Мир, 1939, 360 стр.
2. Н. Вирт Алгоритмы + структуры данных = программы.  – М.: Мир, 1997, 407 стр.
3. Д.Кнут искусство программирования Том 3.  – М:Вильямс,  2-е издание, 2002, 800 стр.
4. http://INTUIT .ru – Интернет-Университет Информационных Технологий

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ПРИЛОЖЕНИЯ

Приложение 1. Исходный код

  uses vcl, utils;

  type