Сортировка массива

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

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

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

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

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

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

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

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 раз, каждый раз уменьшая диапазон просмотра на один элемент.

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

program primer1;

const n = 10;

var a: array[1..n] of integer;

var i,j:integer;

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

begin {main}

   writeln('Введите исходный массив:');

   for i:=1 to n do read(a[i]);

    

 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;

   writeln('Отсортированный массив:');

   for i:=1 to 10 do write(a[i],' ');

   writeln;

end.

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

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

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

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

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

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

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

Решение

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

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

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

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

program primer2;

{Линейная сортировка (сортировка отбором)}

program primer_1;

const n = 10;

var a: array[1..n] of integer;

var i,j:integer;

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

begin {начало тела программы}

  

       writeln('Введите исходный массив:');

       for i:=1 to n do read(a[i]);

  

       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;

   writeln('Отсортированный массив:');

  for i:=1 to n do write(a[i],' ');

   writeln;

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

Номер элемента	1	2	3	4	5
Исходный массив	8	7	5	4	2
Первый просмотр	7	5	4	2	8
Второй просмотр	5	4	2	7	8
Третий просмотр	4	2	5	7	8
Четвертый просмотр	2	4	5	7	8

Видеоурок по сортировке массивов: