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

 

Третий просмотр: рассматриваемая часть массива содержит три первых элемента.

i = l              4   2   5   8   9

                       > меняем

i = 2             2   4   5   8   9

                            < не меняем

Число 5 стоит на своем месте.

 

Четвертый просмотр: рассматриваем последнюю пару.

i = 1             2   4   5   8   9

                                 < не меняем

 

Число 4 стоит на своем месте. Для  самого маленького элемента (2) остается только одно место — первое.

Итак, наш массив отсортирован по возрастанию  элементов методом простого обмена. Этот метод называют также методом «пузырька».

 

 

 

 

 

 

 

 

Опишем процедуру «пузырьковой» сортировки.

Procedure  sorting2(var  a : ar );

var  k ,  i ,  t :  integer;

{k - номер просмотра (изменяется от 1 до n-1),

i - номер рассматриваемой пары,

t - промежуточная переменная для  перестановки местами элементов}

 

Begin

        for   k : = l   to   n - 1   do            {цикл по номеру просмотра}

        for   i :  = l   to   n - k   do

        if   a [ i ] > a [ i + l ]   then           {перестановка элементов}

        Begin

                  t : = a [ i ];  a [ i ] : = a [ i + 1 ];  a [ i + l ] : = t

        End;

End.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

1) выбрать максимальный элемент  массива;

2) поменять его местами с последним элементом (после этого самый большой элемент будет стоять на своем месте);

3) повторить пп.1-2 с оставшимися  n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним (n-1)-м элементом, затем с оставшимися n-2 элементами и так далее, пока не останется один (наименьший) элемент, уже стоящий на своем месте.

 

 

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

Задание:

Пусть исходный массив  a состоит из 10 элементов и имеет вид

                                                  5  13  7  9  1 8 16 4 10 2

 

Решение:

После сортировки массив должен выглядеть  так:

                                                  1 2 4 5 7 8 9 10 13 16

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

1-й шаг: рассмотрим весь массив и найдем в нем максимальный элемент — 16

(стоит на седьмом месте), поменяем  его местами с последним элементом  — с 2.

                                            

Максимальный элемент записан  на свое место.

 

2-й шаг: рассмотрим часть массива — с первого до девятого элемента. Максимальный

элемент этой части — 13, стоящий  на втором месте. Поменяем его местами

с последним элементом этой части  — с 10

                                 

Отсортированная часть массива  состоит теперь уже из двух элементов.

 

3-й шаг: снова уменьшим рассматриваемую часть массива на один элемент. Здесь

надо поменять местами второй элемент (его значение — 10) и последний  элемент

этой части — 4.

                                                                                             

 

5-й шаг: максимальный элемент этой части массива является последним в ней,

поэтому его надо оставить на старом месте.

                                  

 

Далее действуем аналогично.

6-й шаг:

                                  

 

7-й шаг:

                                

 

8-и шаг:

                                            

 

9-й шаг:

                                          

 

Итого:

               1 2 4 5 7 8 9 10 13 16

Для программной реализации этого  процесса необходимо организовать цикл по i — длине рассматриваемой части массива, которая изменяется от n до 2.

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

 

 

Теперь можем записать алгоритм сортировки:

For  i : = n  downto  2  do

Begin

              найти максимальный элемент из а [ 1 ] , . . . , a [ i ];

              запомнить его индекс в переменной  к;

              если i <> k поменять местами a [ i ] и а [к]

End;

 

Опишем этот алгоритм подробно в  виде процедуры:

Procedure  sortingl (var  a : ar);   {поскольку в процессе работы процедуры массив изменится, формальный  параметр а описывается как параметр-переменная}

var  i,  j,  k :  integer;

m:  integer;   {значение максимального элемента рассматриваемой части массива}

Begin                                                                                                                                                

         for  i : = 10  downto  2  do       {цикл по длине рассматриваемой части массива}

                   Begin      {поиск максимального элемента и его номера в текущей части             

                   массива}

                               k : = i; m : = a [ i ];       {начальные значения макс, элемента  и его

                               индекса в рассматриваемой части  массива}

                               for j : = 2  to  i - 1  do

                               if  a [ j ] > m   then

                                        Begin

                                               k : = j;  m : = a [k];

                                        End;

                               if  k <> i  then

                               Begin                    {перестановка элементов}

                                         a [ k ] : = a [ i ] ; a [ i ] : = m

                               End;

                   End;

End.

 

 

 

 

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

 

Сортировка этим методом производится последовательно шаг за шагом. На к-м шаге считается, что часть массива, содержащая первые к-1 элемент, уже упорядочена, то есть        а [ 1 ] ≤ а [ 2 ] ≤...≤ а [ к – 1 ]. Далее необходимо взять к-й элемент и подобрать для него место в отсортированной части массива такое, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое j (1 ≤ j ≤ k – 1 ), что a [ j ] ≤ а [ к ] ≤ a [ j + l ]. Затем надо вставить элемент а [ к ] на найденное место. С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить п-1 шаг.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Задание:

Требуется отсортировать массив из  10 элементов по возрастанию методом прямого включения:

 

Решение:

Рассматриваем часть массива  из одного элемента (13). Надо вставить в  нее второй элемент массива (6) так, чтобы упорядоченность сохранилась. Так как 6 < 13, вставляем 6 на первое место. Отсортированная часть массива содержит два элемента (6 13).

 

Возьмем третий элемент массива (8) и подберем для него место в  упорядоченной части массива. 8 > 6 и  8 < 13, следовательно, его надо вставить на второе место.

 Следующий элемент — 11. Он записывается в

 упорядоченную часть массива на третье место, так как  11 >

 8, но 11 < 13.

 Далее, действуя аналогичным образом, определяем, что 3

 необходимо записать на первое место.

 

 По той же причине 1 записываем на первое место.

 

 Так как 5 > 3, но 5 < 6, то место 5 в упорядоченной части —

 третье.

 

 Место числа 9 — шестое.

 

 Определяем место для предпоследнего элемента 15.

 Оказывается, что этот элемент массива уже находится на

 своем месте.

 Осталось подобрать подходящее место для последнего

 элемента (7).

 Массив отсортирован полностью.

 

 

Сейчас можно коротко описать  фрагмент алгоритма сортировки с  помощью простого включения:

for  k : = 2   tо   n   do   {так  как начинаем сортировку с поиска подходящего места для а [2],  i изменяется от 2 до п}                                                                                                                 

Begin

          x : = a [ k ];

          "вставить  х на подходящее место в  а [ 1 ] , . . . , а [ к ] "

End;

Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента x. Поступим следующим образом: будем просматривать элементы, расположенные левее х (то есть те, которые уже упорядочены), двигаясь к началу массива. Надо просматривать элементы a [ j ],  j изменяется от k - 1 до 1.

Такой просмотр закончится при выполнении одного из следующих условий:

• найден элемент a [ j ] < x, что говорит о необходимости вставки  х между a [ j – l ]  и  a [ j ];

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

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

 

Учитывая это, опишем процедуру  сортировки:

Procedure  Sorting3(var a : ar);

var  k, j, x : integer;

Begin

       for  k : = 2   to  n  do

       Begin

               x : = a [ k ];  j : = k - l;

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

               Begin

                         a [ j + l ]  : = a [ j ];  dec ( j )

               End;

               a [ j + l ] : = x

       End;

End.

 

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

 

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

Пусть массив a [1..n] разбивается на части длиной к, тогда первая часть — а [1], a [2],..., а [к], вторая — а [к+1], а [к+2], ..., а[2к] и так далее. Если п не делится на к, то в последней части будет менее к элементов.

После того как массивы-части упорядочены, можно объединить их в упорядоченные массивы-части, состоящие не более, чем из 2к элементов, которые далее объединить в упорядоченные массивы длиной не более 4к, и так далее, пока не получится один искомый массив.

Таким образом, чтобы получить отсортированный  массив этим методом, надо многократно «сливать» два упорядоченных отрезка массива в один упорядоченный отрезок. При этом другие части массива не затрагиваются.

 

 

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

Задание:

Пусть первая часть массива (часть a) состоит из пяти элементов:

                                    ... 3   5   8   11   16 ...,

а вторая часть (часть b) — из восьми элементов:

                              ... 1   6   7   9   12   13   18   20...

По условию оба массива-части упорядочены. Сформировать массив с, который будет содержать 13 элементов.

 

Решение:

Введем обозначения:

• i — номер обрабатываемого  элемента части a;

• j - номер обрабатываемого элемента части b;

• l — номер заполняемого элемента массива c.

Поскольку заполнение массива  c  ведется с его начала, на первом шаге значение  l = 1.

 

1-й шаг: на первое место в массиве c  претендуют а [k + 1] = 3  и b [m + 1] = 1

(i = k + 1, j = m + 1). Так как 1 < 3, в  массив  c  надо занести 1 и  перейти к следующему

элементу части b, то есть увеличить  j  на 1 (значение j  станет равно  т + 2), а  также увеличить на 1 значение l (значением l будет 2).

 

2-й шаг: теперь надо сравнить а [k + 1] = 3  и  b [m + 2] = 5.  3 < 5, следовательно, на