Среда программирования Free Pascal, методы сортировки

Федеральное агентство по образованию

ГОУ ВПО Тульский государственный педагогический

университет им. Л. Н. Толстого

Курсовая работа  на тему:

Среда программирования Free Pascal

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

                             Выполнила:

                                                                     студентка ф-та МФиИ  гр. 3 Б      

                                                                     Сидорова С. А.                  

                         Проверила:

                                                                      к. п. н., доцент кафедры

                                                                      информатики и МОИ

                                                                      Сорокина Н. В.

Тула 2009

   Содержание

     Введение                                                                                                                           3

1.  Сортировка вставками                                                                                                      4

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

3.  Сортировка методом прямого включения                                                                    14

4.  Сортировка методом слияния                                                                                       17

5.  Обменная сортировка с разделением                                                                            20

     Заключение                                                                                                                     23

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

Введение

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

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

Таким образом, Free Pascal обладает рядом возможностей, очень удобных для пользователя при составлении программ по сортировкам. Для решения задач удобно сначала упорядочить данные по определенному признаку. А процесс упорядочения заданного множества объектов по заданному признаку и называется сортировкой. Поэтому темой нашей курсовой работы была выбрана: «Среда программирования Free Pascal. Методы сортировки».

В данной курсовой работе будут рассмотрены основные виды сортировок с  подробными описаниями и примерами решения задач, выполненных в среде программирования Free Pascal.

1. Сортировка вставками (метод «пузырька»)

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

Итак, пусть требуется расположить в порядке неубывания (речь идёт о сортировке «по неубыванию», а не о сортировке «по возрастанию», поскольку в массиве могут быть элементы с одинаковыми значениями) n элементов массива a, содержащего вещественные числа. Запишем описание типа массива (при выборе названия типа для массива использовался принцип «венгерской нотации». Первая строчная буква t в имени типа tArray подчёркивает природу этого наименования (t – от type). Такой принцип обозначений был предложен сотрудником Microsoft, венгром по происхождению, Чарльзом Симонаи (Charles Simonyi)):

const

     nmax =  10000;

type

     tArray = array [l..nmax]  of  real;

Сортировка вставками - это простой и очень естественный алгоритм упорядочения. Именно таким способом мы часто выполняем сортировку вручную.

Для упорядочения по неубыванию элементов массива поступим так (рис. 1): выберем второй по порядку элемент и разместим его должным образом по отношению к первому. То есть если значение второго элемента больше или равно значению первого, то второй оставляем на своем месте, если нет — расположим его перед первым, сдвигая первый на второе место. Теперь первые два элемента упорядочены. Берем следующий, третий и вставим его в нужное место по отношению к первым двум. Теперь упорядочены первые три. Берем поочередно следующие, вплоть до последнего, и помещаем каждый в нужное место уже упорядоченной последовательности предыдущих. Отыскивая подходящее место для данного элемента, можно просто последовательно просматривать предшествующие, начиная с того, который расположен перед выбранным. Как только встречается элемент со значением меньшим или равным выбранному, помещаем выбранный сразу за таким элементом. В процессе просмотра и движения в сторону меньших номеров (влево на схеме) сдвигаем вправо на одну позицию каждый элемент, который будет располагаться правее выбранного в упорядоченном массиве.

Запишем этот алгоритм на Паскале. Обозначим i — номер выбранного элемента; х — значение i-го элемента.

for  i : = 2  to n do begin

x : = a [ i ];

{Вставить  x  в  последовательность предшествующих  ему  элементов}

end;

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

{Сортировка   простыми вставками}

procedure   InsSort (var  a:   tArrav;   n :   integer);

var

      i,    j    :   integer;

      x   :   real;

begin

       for   i   : =   2   to   n   do  begin

   x   : =   a [ i ];                   {выбор  элемента}

    j   : =   i  -  1;

while (j > 0)  and  (x > a [ j ])  do  begin

                     a [ j + l ] : = a [ j ];      {сдвиг вправо}

                      j : = j - 1;     {движение влево}

   end;

   a [ j + l ] : = x;       {x попадает на свое место}

      end;

end;

Использованная запись условия в цикле while предполагает, что действует короткая схема вычисления логических выражений, то есть если условие (j>0), записанное перед and, не выполняется, то условие, записанное после and, вообще не проверяется, а, значит, не происходит и обращения к несуществующему (нулевому) элементу массива. Левая часть составного условия как бы защищает правую от вычисления при недопустимом значении j. Современные компиляторы Паскаля обеспечивают вычисления по короткой схеме.

Можно попытаться ускорить работу программы, а заодно избавиться от опасности обращения к несуществующему элементу массива. Для этого дополним массив нулевым элементом, для чего придется изменить описание типа:

type

      tArray = array   [0..nmax]   of   real;

Сортировать при этом по-прежнему будем элементы с номерами от 1 до n, а элемент а [0] будет исполнять роль барьера. Перед каждым циклом вставки будем помещать в элемент а [0] значение х. Это позволит упростить условие внутреннего цикла, отказавшись от проверки (j >0). Корректное завершение цикла при этом гарантируется тем, что при сравнении х с a [0] условие х < а [j]  нарушается, поскольку при  j = 0 значение х будет равно а [0]. Барьер не преодолеть. Проверка условия цикла выполняется многократно, и его упрощение позволяет надеяться на заметное ускорение работы программы.

{Сортировка вставками с барьером}

procedure   InsSort (var  a:   tArray;   n:   integer);

var

      i,   j    :   integer;   

      x   :   real;

begin

      for  i : = 2  to  n  do  begin

             x : = a [ i ] ;

             a [ 0 ] : = x;     {установка барьера}

              j : = i - 1;

             while  x < a [ j ]   do  begin

             a [ j + l ]  : =  a [ j ];         {сдвиг вправо}

              j : =  j - 1;            {движение влево}

             end;

             a [ j + l ]  : =  x;               {x попадает на  свое  место}

     end;

end;

Наконец, можно заметить, что от переменной х можно вообще отказаться, сэкономив на присваивании ей значения. Роль х будет исполнять а [0]. При этом можно рассчитывать, что время обращения к элементу массива а [0] будет не больше времени доступа к неиндексированной переменной х. Большинство компиляторов обращается с элементами массивов, имеющими константные индексы, как с простыми переменными.

{Сортировка вставками с барьером. Вариант 2}

procedure InsSort (var a: tArray;   n: integer);

var                                                                                                                                                       

        i, j : integer;

begin

        for  i : = 2  to  n  do  begin

              a [ 0 ] : =  a [ i ];       {установка барьера}

                j : = i - 1;

               while  a [ 0 ] < a [ j ]  do  begin

                          a [ j + l ] : = a [ j ];           {сдвиг вправо}

                           j : = j - 1;       {движение влево}

               end;

                a [ j + l ] : = a [ 0 ];       {a [ i ]  попадает на свое место}

end;

end;

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

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

{Сортировка  короткого частично  упорядоченного массива}

procedure  InsSort(var a: tArray;  n: integer);

var

         i, j : integer;

         x : real;

begin

         for i : = 2  to  n  do  begin

                 x : = a [ i ] ;

                 if  x < a [ i – l ]  then  begin

                           a [ i ] : = a [ i - 1 ];  

                            j  : =   i - 2;

                            while  ( j > 0 )   and   ( x < a [ j ] )   do begin

                                             a [ j + 1 ]    : =   a [ j ];           {сдвиг вправо}                                    

                                                          j  : =  j - 1;            {движение  влево}

                            end;

                            a [ j + l ]  : =   x;               {x попадает на  свое место}

     end;

         end;

end;

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

К этому варианту можно применить идею барьера, но если имеется в виду сортировка подмассивов, то для барьера нет места.

Пример решения задачи.

Задание:

Отсортировать по возрастанию методом простого обмена массив из пяти элементов:

                                                          5 18 4 9.

Решение:

Длина текущей части массива —  n – k + 1, где k — номер просмотра, i — номер проверяемой пары, номер последней пары — n - k. За вертикальной чертой располагаются отсортированные элементы.

Первый просмотр: рассматривается весь массив.

i = 1              5   4   8   2   9

                        > меняем

i = 2              4   5   8   2   9

                             < не меняем

i = 3              4   5   8   2   9