Пятница, 29.03.2024, 08:39
Блог учителя информатики и математики
О блогеМой профильРегистрацияВыходВход
Вы вошли как Гость · Группа "Гости" Приветствую Вас, Гость · RSS
Меню блога
Погода в нашем районе.

НАГРАДА

Как Вы считаете, должны ли дети ходить в школу в школьной форме?
Всего ответов: 2806
 
 Блог учителя
Главная » Статьи » Информатика » В помощь ученику

Сортировка пузырьком. (12 урок)
Методы сортировки массивов


Сортировкой  называется расположение его элементов по возрастанию или убыванию. Если не все элементы различны, то надо говорить о неубывающем или невозрастающем порядке.

Метод "пузырька"
Самым простым методом сортировки является так называемый метод "пузырька". Представьте , что массив расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с «нижними». 
(Если встречается более "легкий" элемент, то они меняются местами.
Если встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .)

Алгоритм и особенности этой сортировки:

  1. При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
  2. Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
  3. При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
  4. На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
  5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
  6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.
  7. Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
  8. При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.




В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время 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. Вывести его на экран. Отсортировать его методом простого обмена ("пузырька”) по убыванию и вывести отсортированный массив на экран.





Категория: В помощь ученику | Добавил: Harchev (20.11.2013)
Просмотров: 3859 | Комментарии: 13 | Рейтинг: 3.8/36
Всего комментариев: 13
1 Катерина  
Решение ДЗ. Найти самый часто встречающийся элемент из массива. 

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]
);
End.

2 Настя  
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.

10 Harchev  
отлично

3 Ангелина  
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.

4 Ангелина  
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.

9 Harchev  
Заголовок опять с ошибкой

5 Лавриненко Михаил  
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.

6 Ангелина  
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.

11 Harchev  
Сдай зачёт по этой программе.

7 Дмитрий.г  
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.

8 Аркадий  
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.

12 Анастасия Степаненко  
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.

13 irina  
спасибо за урок

Имя *:
Email *:
Код *:
Copyright MyCorp © 2024
Блог учителя Учительский портал