Сортировка одномерного массива

Сортировкой называют набор операций, упорядочивающий элементы массива в соответствии с заданным отношением порядка. Например, в упорядоченном массиве A по возрастанию выполняются неравенства вида:

 

A₁ < A₂ < … < A_n-1 < A_n

 

Вопрос о возрастании или убывании упорядоченного массива для нас не принципиален. Как правило, программы, сортирующие массив по возрастанию, легко изменяются для сортировки по убыванию.

Существует множество алгоритмов сортировки (пузырьковая сортировка, сортировка по дереву, быстрая сортировка, сортировка слиянием, сортировка Шелла и т. д.), они имеют большую практическую значимость, являются фундаментальными в некоторых областях информатики.

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

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

Суть алгоритма такова. Начиная с первого, сравниваются два соседних элемента массива A[i] и A[i+l], если A[i] > A[i+1], то элементы меняются местами. В первый раз мы проходим массив начиная с индекса 1, до индекса n - 1, во второй - с 1 до n - 2 и т. д. Любой массив будет отсортирован за n-1 проходов. Таким образом, порядок сложности данного алгоритма (максимальное количество операций проверок и перестановок элементов массива) пропорционален n²/2, хотя массив может быть отсортирован уже после первого прохода.

 

program p8_2;

const

n = 10; { Константа n задаёт количество элементов в массиве А}

var

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

i, j : integer;

temp : Real;

begin

{ ввод элементов массива }

Writeln (' введите ', n, ' элементов массива: ' ) ;

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

{ вывод элементов массива на экран }

Writeln (' Массив до сортировки:' ) ;

for i:= 1 to n do Write(А[i] : 6 : 2, ' ');

Writeln; { Перевод курсора в следующую строку }

{ сортировка }

For j := 1 to n-1 do { цикл перебирает проходы по массиву }

For i : = 1 to n - j do { цикл перебирает пары элементов массива }

if A[i] > A[i + 1] then

begin { ... если A[i] > A[i+1] , то элементы меняются местами }

temp : = A [i+1] ;

A[i+1] := A[i];

A[i] := temp;

end;

{ выводим на экран отсортированный массив }

Writeln (' Массив после сортировки:' ) ;

for i:= 1 to n do Write (A [i] : 6 : 2, ' ') ;

Writeln;

end.