Сортировкой называется расположение его элементов по возрастанию или убыванию. Если не все элементы различны, то надо говорить о неубывающем или невозрастающем порядке.
Метод "пузырька"
Самым простым методом сортировки является так называемый метод "пузырька". Представьте , что массив расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с «нижними».
(Если встречается более "легкий" элемент, то они меняются местами.
Если встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .)
Алгоритм и особенности этой сортировки:
При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.
Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.
В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.
Вот текст программы упорядочения массива M[1..N]:
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 — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.
Применение метода "пузырька" можно проследить здесь.
Задача 1.
const
m = 10;
var
arr: array[1..m] of integer;
i, j, k: integer;
begin
randomize;
write ('Исходный массив: ');
for i := 1 to m do begin
arr[i] := random(256);
write (arr[i]:4);
end;
writeln; writeln;
for i := 1 to m-1 do
for j := 1 to m-i do
if arr[j] > arr[j+1] then begin
k := arr[j];
arr[j] := arr[j+1];
arr[j+1] := k
end;
write ('Отсортированный массив: ');
for i := 1 to m do
write (arr[i]:4);
writeln;
readln
end.
Составьте условие решенной задачи.
ДЗ.Задача 2.
Создать массив целых чисел из N=15 элементов. Заполнить его случайным образом, числами, в диапазоне от 0 до 40. Вывести его на экран. Отсортировать его методом простого обмена ("пузырька”) по убыванию и вывести отсортированный массив на экран.
Решение ДЗ. Найти самый часто встречающийся элемент из массива.
Var a : Array[1..10] Of integer; i, j, m, n, p : integer; Begin writeln('введите 10 элементов массива'); For i := 1 To 10 Do readln( a ); m := 1; p := 1; For i := 1 To 10 Do Begin n := 0; For j := 1 To 10 Do Begin If a = a
Then inc(n); End; If n > m Then Begin m := n; p := i; End; End; writeln('самый часто встречающийся элемент :', a[p]
const n=10; var a:array[1..n] of integer; b:array[0..100] of integer; i,l,m:integer; begin writeln('Введите элементы в массив'); for i:=1 to n do begin read(a[i]); end; for i:=0 to 100 do b[i]:=0; for i:=1 to n do b[a[i]]:=b[a[i]]+1; l:=0; for i:=0 to 100 do if b[i]>l then begin l:=b[i]; m:=i; end; writeln('Наиболее часто встречается ',m,' - ',l,' рaз(а)'); writeln('P. S. Если в массиве наиболее часто встречается несколько элементов(с одинаковым числом повторений), то выводится элемент, стоящий первее!!!'); end.
element massiva Var a : Array[1..24] Of integer; i, l, m, r, p : integer; Begin writeln('введите 24 элементf массива'); For i := 1 To 24 Do readln( a[i] ); m := 1; p := 1; For i := 1 To 24 Do Begin r := 0; For l := 1 To 24 Do Begin If a[i] = a[l] Then inc(r); End; If r > m Then Begin m := r; p := i; End; End; writeln('самый часто встречающийся элемент :', a[p]); End.
program element massiva; Var a : Array[1..24] Of integer; i, l, m, r, p : integer; Begin writeln('введите 24 элемента массива'); For i := 1 To 24 Do readln( a[i] ); m := 1; p := 1; For i := 1 To 24 Do Begin r := 0; For l := 1 To 24 Do Begin If a[i] = a[l] Then inc(r); End; If r > m Then Begin m := r; p := i; End; End; writeln('самый часто встречающийся элемент :', a[p]); End.
uses Crt; var x:real; i:integer; a:array [1..7] of integer; begin clrscr; x:=0; writeln('введите температуру за каждый день недели'); for i:=1 to 7 do begin readln(a[i]); x:=+a[i]; end; x:=x/7; write('средняя температура = ',x); end.
program element_massiva; Var a : Array[1..24] Of integer; i, l, m, r, p : integer; Begin writeln('введите 24 элемента массива'); For i := 1 To 24 Do readln( a[i] ); m := 1; p := 1; For i := 1 To 24 Do Begin r := 0; For l := 1 To 24 Do Begin If a[i] = a[l] Then inc(r); End; If r > m Then Begin m := r; p := i; End; End; writeln('самый часто встречающийся элемент :', a[p]); End.
uses crt; const n=40; var a:array[1..n] of byte; b:array[0..200] of byte;{массив встречаемости элементов} i,mx,imx:byte; begin clrscr; randomize; writeln('Исходный массив:'); for i:=1 to n do begin a[i]:=random(201); write(a[i]:4); end; writeln; for i:=0 to 200 do b[i]:=0; for i:=1 to n do inc(b[a[i]]); mx:=0; for i:=0 to 200 do if b[i]>mx then begin mx:=b[i]; imx:=i; end; write('Наиболее часто встречается элемент ',imx,' ',mx,' рз.'); end.
Program fyhb uses crt; const n=40; var a:array[1..n] of byte; b:array[0..200] of byte;{массив встречаемости элементов} i,mx,imx:byte; begin clrscr; randomize; writeln('Исходный массив:'); for i:=1 to n do begin a[i]:=random(201); write(a[i]:4); end; writeln; for i:=0 to 200 do b[i]:=0; for i:=1 to n do inc(b[a[i]]); mx:=0; for i:=0 to 200 do if b[i]>mx then begin mx:=b[i]; imx:=i; end; write('Наиболее часто встречается элемент ',imx,' ',mx,' рз.'); end.
Uses crt; Var a : Array[1..50] Of integer; i, l, m, r, n : integer; Begin clrscr; writeln('введите 50 элементов массива'); For i := 1 To 50 Do readln( a[i] ); m := 1; n := 1; For i := 1 To 50 Do Begin r := 0; For l := 1 To 50 Do Begin If a[i] = a[l] Then inc(r); End; If r > m Then Begin m := r; n := i; End; End; writeln('часто встречающийся элемент массива:', a[n]); End.
