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

    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