Сортировка методом прямого обмена

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

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

Просматривая массив от первого элемента, найти минимальный и поместить его на место первого элемента, а первый на место минимального.

Просматривая массив от второго элемента, найти минимальный и поместить его на место второго элемента, а второй на место минимального.

И так далее до предпоследнего элемента.

Ниже представлена программа сортировки массива целых чисел по возрастанию. Для демонстрации процесса сортировки программа выводит массив после каждого обмена элементов.

CONST

size = 5 ;

VAR

A : Array[1..5] of Integer ;

i : Integer ; { номер эл-та, от которого ведется поиск минимального эл-та }

min : Integer ; { номер минимального эл-та в части массива }

{ от i до верхней границы массива }

j : Integer ; {номер эл-та, сравниваемого с минимальным }

buf : Integer ; {буфер, используемый при обмене эл-тов массива }

k : Integer ;

BEGIN

Write(‘ Введите’,size:3,’ целых в одной строке через пробел ‘) ;

For k := 1 to size do read(A[k]);

writeln(‘ Сортировка ‘) ;

For i := 1 to size-1 do

Begin

{поиск минимального эл-та в части массива от A[i] до A[size]}

min := i ;

for j := i+1 to size do begin

if A[j]<A[min] then min := j ;

{ поменяем местами A[min] и A[i] }

buf := A[i] ;

A[i] := A[min] ;

A[min] := buf ;

{ выведем массив }

for k:=1 to size do write(A[k],’ ‘) ;

writeln ;

end ;

end ;

writeln( ‘ Массив отсортирован ’ ) ;

END.

В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением ¾ к концу массива (тонут), поэтому этот метод иногда называют “пузырьковым”. Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.

На рис. 17 показан пример сортировки массива. Буквой (“а”) обозначено исходное состояние массива и перестановки на первом проходе, буквой (“б”) ¾ состояние после перестановок на первом проходе и перестановки на втором проходе и так далее.

Рис.17. Процесс сортировки массива.

Ниже представлена программа сортировки массива целых чисел по возрастанию. Для демонстрации процесса сортировки программа выводит массив после каждого цикла обменов.

CONST

size = 5 ;

VAR

A : Array[1..5] of Integer ;

i : Integer ; { счетчик циклов}

k : Integer ; { текущий индекс элемента массива ]

buf : Integer ;

BEGIN

WriteLn( ‘ Сортировка массива пузырьковым методом’) ;

Write(‘ Введите’,size:3,’ целых в одной строке через пробел ‘) ;

For k := 1 to size do read(A[k]);

writeln(‘ Сортировка ‘) ;

for i := 1 to size-1 do begin

for k := 1 to size-1

do begin

if A[k] > A[k+1]

then begin

{обменяем k-ый и (k+1)-ый элементы}

buf := A[k} ;

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

A[k+1] := buf ;

end ;

end ;

for k := 1 to size do write(A[k],’ ‘) ;

writeln ;

end ;

writeln(‘ Массив отсортирован ‘) ;

END.