Метод "пузырька"По-видимому, самым простым методом сортировки является так называемый метод "пузырька". Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередносравнивается с последующими. При этом: если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами; при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .
В результате наибольший элемент оказывается в самом верху массива. Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д. Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j. ПРОГРАММА. ПУЗЫРЬКОВАЯ СОРТИРОВКА. PROGRAM BS; VAR I,J,X,N:INTEGER; M:ARRAY[0..50] OF INTEGER; BEGIN WRITELN('Введи длину массива'); READ(N); WRITELN('Введи массив'); FOR I:=1 TO N DO READ(A[I]); FOR I:=2 TO N DO FOR J:=N DOWNTO I DO IF M[J-1]>М[J] THEN BEGIN X:=M[J-1]; M[J-1]:=M[J]; M[J]:=X END; WRITELN('Результат:'); FOR I:=1 TO N DO WRITE(M[I],' ') END. Пример программы упорядочения массива с использование подпрограммы swap begin
for j:=1 to N-1 do
for i:=1 to N-j do
if M[i] > M[i+1] then
swap(M[i],M[i+1])
end; |
Стандартная процедура swap будет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами: procedure swap(var x,y: ...);
var t: ...;
begin
t := x;
x := y;
y := t
end; |
Заметим, что если массив M — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.
| 
