Разбор решений олимпиадных задач по программированию

Сортировка массива

Сортировка (упорядочивание) –

процесс размещения элементов заданного множества объектов в некотором определенном порядке, как правило, в порядке возрастания или убывания.

• p(i) ≤ p(i+1) – упорядоченность по возрастанию; p(i) ≥ p(i+1) – упорядоченность по убыванию.
• p(i) ≤ p(i+1) – упорядоченность по возрастанию;
• p(i) ≥ p(i+1) – упорядоченность по убыванию.

В основе алгоритма лежит обмен соседних элементов массива.

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

Таким образом, элементы с меньшим значением продвигаются к началу массива, а элементы с большим значением – к концу массива (всплывают), поэтому этот метод иногда называют методом “пузырька”.

38

3

59

53

51

27

50

44

42

1

36

14

33

8

10

4

16

21

24

31

36

59

53

51

27

50

44

42

38

33

3

24

21

16

14

10

8

4

31

1

50

42

44

36

27

51

53

59

38

1

33

10

31

4

8

3

14

16

21

24

59

53

51

27

50

36

44

42

38

16

33

8

31

3

4

1

10

21

14

24

33

53

51

50

44

42

38

36

59

31

4

24

1

3

27

8

14

16

21

10

36

59

53

51

27

50

44

42

38

24

33

31

21

16

10

8

4

3

1

14

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

В разделе описания данных задается массив размерностью 20 ячеек:

a:array [1..20] of integer;

Исходный массив заполняется через цикл с заданным числом повторений при помощи оператора случайных чисел:

for i:=1 to 20 do

a[i]:=random(10);

После заполнения массива случайными числами массив выводим на монитор (для самопроверки):

for i:=1 to 20 do

write (a[i]:3);

a[i+1] then и меняя их местами в случае истинности условия (как -?)" width="640"

Если будем пробегать по длине массива от первого до последнего

for i:=1 to 20 do,

и сравнивая каждый раз величины рядом стоящих элементов

if a[i]a[i+1] then

и меняя их местами в случае истинности условия (как -?)

Перестановка элементов в массиве

A[i]

A[i+1]

2

3

1

P

a[i+1] then begin p:=a[i]; a[i]:=a[i+1]; a[i+1]:=p; end; 19" width="640"

Таким образом получим:

for i:=1 to 20 do

if a[i]a[i+1] then begin

p:=a[i];

a[i]:=a[i+1];

a[i+1]:=p;

end;

19

Прохождения за один раз недостаточно для полного упорядочивания массива. Необходимо установить признак завершения работы f (флаг), который будет принимать значение f:=0 каждый раз перед упорядочиванием массива. Если свершается хотя бы одна перестановка, признак (флаг) переходит в состояние 1. Так будет повторяться до тех пор, пока во время прохождения по массиву не произойдет ни одной замены, и переменная f не останется в 0 состоянии. Чтобы первый раз принудительно отправить массив на сортировку, мы флаг переводим в состояние 1

a[i+1] then begin p:=a[i]; a[i]:=a[i+1]; a[i+1]:=p; f:=1 ; end; end;" width="640"

f:=1;

while f=1 do begin

f:=0;

for i:=1 to 19 do

if a[i]a[i+1] then begin

p:=a[i];

a[i]:=a[i+1];

a[i+1]:=p;

f:=1 ;

end;

end;

Чтобы проверить правильность сортировки, необходимо вывести массив после сортировки на монитор:

write('массив после обработки');

writeln;

for i:=1 to 20 do

write(a[i]:3);

a[i+1] then begin p:=a[i]; a[i]:=a[i+1]; a[i+1]:=p; f:=1 ; end; end; вывод массива после сортировки writeln; write('массив после обработки'); writeln; for i:=1 to 20 do write(a[i]); End." width="640"

Общий вид программы по сортировке массива примет вид:

program sortirovrk_puzir;

var

a:array [1..20] of integer;

i,f,p:integer;

begin

заполнение массива

for i:=1 to 20 do

a[i]:=random(10);

вывод на монитор массива до обработки

write ('массив до обработки');

writeln;

for i:=1 to 20 do

write (a[i]);

сортировка массива

f:=1;

while f=1 do begin

f:=0;

for i:=1 to 19 do

if a[i]a[i+1] then begin

p:=a[i];

a[i]:=a[i+1];

a[i+1]:=p;

f:=1 ;

end;

end;

вывод массива после сортировки writeln;

write('массив после обработки'); writeln;

for i:=1 to 20 do

write(a[i]);

End.

Сортировка методом «пузырька» (наиболее простой, но и самый неэффективный, медленный способ).

• Проверить работоспособность данной программы
• Выяснить, какие еще способы сортировки массива существуют
• Написать программу, которая сортирует массив из 40 элементов по убыванию методом «пузырька» и считает при этом количество произведённых перестановок .
• Стр.335 – 340, упр. 1-6.