Урок 28. Сортировка массива

Урок из серии: «Программирование на языке Паскаль»

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

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

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

При сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального)  элемента и его номера.

Алгоритм сортировки массива методом выбора:

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

Для упорядочения массива потребуется (n-1) просмотров массива. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная, соответственно, уменьшаться.

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

Задача 1. Массив из 10 элементов отсортировать по возрастанию методом простого перебора.

Решение

Напишем процедуру. Входным параметром для неё будет массив. Он же будет и выходным параметром. Поэтому описываем его как параметр-переменная (с ключевым словом var).

В процедуре внешний цикл по i — определяет длину рассматриваемой части массива. Она будет  изменяться от n до 2.

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

Программный код процедуры:

Procedure sorting1(var a:myarray);
{Сортировка по возрастанию методом простого выбора}
var i,j:integer;
    k,m:integer; {номер и значение максимального элемента}
begin
   for i:= n downto 2 do{задаем длину рассматриваемой части массива}
      begin
        {ищем максимальный элемент и его номер}
        k:=i; m:=a[i];         for j:= 1 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;
end;

Программный код основной программы:

program primer_1;

const n = 10;
type myarray = array[1..n] of integer;
var a:myarray;
Procedure sorting1(var a:myarray);
{Линейная сортировка (сортировка отбором)}
...
begin {main}
   writeln('Введите исходный массив:');
   for i:=1 to n do read(a[i]);
   sorting1(a);
   writeln('Отсортированный массив:');
   for i:=1 to 10 do write(a[i],' ');
   writeln;
end.

Процесс упорядочения элементов в массиве по возрастанию методом отбора:

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

Сортировка массива методом простого обмена (методом пузырька)

Наиболее известным методом сортировки является сортировка пузырьковым методом. Его популярность объясняется запоминающимся названием и простым алгоритмом.

Метод основан на том, что в процессе исполнения алгоритма более «легкие» элементы массива постепенно «всплывают».

Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Выполняется несколько последовательных просмотров  массива от начала к концу. Если соседние элементы расположены «неправильно», то они меняются местами.

Алгоритм сортировки массива по возрастанию методом простого обмена:

1. Начнем просмотр с первой пары элементов ( a[1] и a[2] ). Если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару элементов ( a[2] и a[3] ), если второй больше третьего, то также меняем их, далее сравниваем третий и четвертый, и если третий больше четвертого, меняем их местами, и т.д. Последними сравниваем (n-1)-ый и n-ый  элементы.При первом обходе массива будут просмотрены все пары элементов массива a[i] и a[i+1] для i от 1 до (n-1). В результате максимальный элемент массива переместится в конец массива.
2. Поскольку самый большой элемент находится на своем месте, рассмотрим часть массива без него, то есть с первого до (n-1) — го элемента.Повторим предыдущие  действия для этой части массива, в результате чего второй по величине элемент массива переместится на последнее место рассматриваемой части массива, то есть на ( n-1 ) — е место во всем массиве.
3. Эти действия продолжают до тех пор, пока количество элементов в текущей части массива не уменьшится до двух. В этом случае необходимо выполнить последнее сравнение и упорядочить последние два элемента.

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

Ниже приведен текст процедуры сортировки массива по возрастанию методом пузырька.

procedure sorting2(var a:myarray);
var k,i,t:integer;
begin
  for k := 1 to n-1 do     {цикл по номеру просмотра}
    for i:=1 to n-k do
       {Если текущий элемент больше следующего, поменять местами}
       if a[i] > a[i+1] then
          begin
            t:=a[i];
            a[i]:=a[i+1];
            a[i+1]:=t;
          end;
end;

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

Процесс упорядочения элементов в массиве по возрастанию методом обмена: