Лекция: Алгоритмы сортировки одномерных массивов

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

Обменная сортировка (метод «пузырька»).

Алгоритм начинается со сравнения 1-го и 2-го элементов массива.

Если 2-й элемент меньше 1-го, то они меняются местами. Этот процесс повторяется для каждой пары соседних элементов массива, пока все N элементов не будут обработаны. За один «проход» массива самый большой элемент встанет на старшее (N-е) место. Далее алгоритм повторяется, причем на р-м «проходе» первые (N-p) элементов сравниваются со своими правыми соседями. Если на очередном «проходе» перестановок не было, то алгоритм свою работу закончил. Таким образом, самые «легкие» элементы впроцессе исполнения алгоритма постепенно «всплывают».

Пример: Отсортировать по возрастанию 20 элементов одномерного массива. Ввод массива осуществить любым способом.

program BubbleSort;

M: array[1..n] of Real;

Var B: Real; i,j: Integer;

begin

n: = 20;

Writeln ('Введите элементы массива:');

for i:=1 to n do Read (M[i]);

for j:=n downto 2 do

for i:=1 to j-1 do

if M[i] > M[i+1] then begin B := M[i];M[i] := M[i+1];M[i+1] := B end;

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