Сортировка массивов (ранжирование)

Рассмотрим два метода сортировки: линейную (сортировка отбором) и пузырьковую.

Оба эти метода не очень эффективны и на практике используются редко, но когда надо отсортировать 20-25 чисел, они вполне эффективны.

Пример. Ввести n чисел. Отсортировать по возрастанию значений. Распечатать неранжированный массив (до сортировки) и ранжированный массив (после сортировки).

1). Алгоритм линейной сортировки.

Сравнить каждый элемент массива с MAS[1].

Если этот элемент меньше, то поменять его местами с MAS[1]. Если больше или равен – ничего не делать. Затем повторить этот процесс, начиная с позиции 2 и так до конца ряда.

Пример. N=5.

1 проход

14 105 11 4 21

 

14 105 11 4 21

11 105 14 4 2

4 105 14 11 21

 

4 105 14 11 21

2 проход

(4) 105 14 11 21

(4) 14 105 11 21

 

(4) 11 105 14 21

 

(4) 11 105 14 21

3 проход

(4) (11) 105 14 21

 

(4) (11) 14 105 21

 

(4) (11) 14 105 21

 

4 проход

(4) (11) (14) 105 21

 

(4) (11) (14) 21 105

 

Program sort1;

Type

Size = 1…100;

Mas = array [size] of integer;

Var

Numb : mas;

Pass, I, n : size;

Temp : integer;

Begin

Writeln (’Укажите количество сортируемых элементов’);

Readln(n);

{Ввод массива}

For i:=1 to n-1 do

For pass:=i+1 to n do

If numb[i]>numb[pass] then

Begin

Temp:=numb[i];

numb[i]:= numb[pass];

numb[pass]:= Temp

End;

For i:=1 to n do

Write (numb[i],’ ‘);

Writeln

end.

 

Независимо от первоначального расположения элементов ряда для их сортировки линейным методом требуется одно и тоже число сравнений.

 

2) Алгоритм пузырьковой сортировки.

Повторять следующий многоходовой процесс до тех пор, пока не будет зарегистрирован проход, на котором не было ни одной перестановки.

Сравнить смежные элементы (numb[1] с numb[2] …….. numb[n-1] с numb[n]). Если они стоят в обратном порядке, поменять местами.

 

1 проход

14 105 11 4 21

 

14 105 11 4 21

 

14 11 105 4 21

 

14 11 4 105 21

 

14 11 4 21 105

 

2 проход

14 11 4 21 105

 

11 14 4 21 105

 

11 4 14 21 105

 

11 4 14 21 105

 

11 4 14 21 105

 

 

3 проход

11 4 14 21 105

4 11 14 21 105

 

4 11 14 21 105

 

4 11 14 21 105

4 11 14 21 105

 

4 проход

4 11 14 21 105

4 11 14 21 105

 

4 11 14 21 105

 

4 11 14 21 105

4 11 14 21 105

 

Это более изящный метод сортировки. Это – многоходовый процесс попарного сравнения соседних элементов. С каждым проходом в старшие позиции будут последовательно перемещаться элементы с максимальными значениями.

 

Program sort2;

Type

Size = 1…100;

Mas = array [size] of integer;

Var

Numb : mas;

Pos : size;

Temp : integer;

Switch : boolean;

Begin

Writeln (’Укажите количество сортируемых элементов’);

Readln(n);

{Ввод массива}

Repeat

Switch:=false;

For pos:=1 to n-1 do

If numb[pos]> numb[pos+1] then

Begin

switch:= true;

temp:=numb[pos];

numb[pos]:=numb[pos+1];

numb[pos+1]:= temp

End;

Until switch =false

End.

Процедуры и функции

Подпрограммы

Процедуры и функции аналогичны программам в миниатюре и имеют общее название – подпрограммы (п/п). Применение п/п дает возможность:

· уменьшить число повторений одной и той же последовательности операторов;

· конструировать программу как совокупность отдельных блоков.

 

Блок В2

Блок В1

Блок В21

Блок В

Блок А1 Блок А2

Блок А

Пример структурированный программы

 

 

 

Достоинством нисходящего программирования (разбивка программ на блоки) является повышение надежности программы, т.к. отдельный блок можно программировать и тестировать отдельно от других блоков.

В программе описание процедур и функций должно располагаться в разделе объявлений программы. Каждая подпрограмма определяется один раз, но может быть использована многократно. Структура подпрограммы аналогична структуре полной программы на языке Т-П, но заканчивается END;.

Описать блок значит указать его заголовок и тело:

PROCEDURE A;

В заголовке указываются имя блока и формальные параметры, если таковые есть. Тело блока подобно телу любой программы.