Алгоритм 2. Пузырьковая сортировка
Реализация данного метода не требует дополнительной памяти. Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами. Эти действия продолжаем, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма Так как каждый раз на свое место становится по крайней мере один элемент, то не потребуется более N проходов, где N — количество элементов. Вот как это можно реализовать:
Program BubbleSort;
Var A : array[1..1000] of integer;
N,i,j,p : integer;
Begin
{Определение размера массива A (N) и его заполнение} … {сортировка данных} for i:=1 to n do
for j:=1 to n-i do
if A[j]>A[j+1] then
begin {Обмен элементов} p:=A[j];
A[j]:=A[j+1];
A[j+1]:=P;
end;
{Вывод отсортированного массива A} … End.
|
