Сортировка массивов (ранжирование)
Рассмотрим два метода сортировки: линейную (сортировка отбором) и пузырьковую.
Оба эти метода не очень эффективны и на практике используются редко, но когда надо отсортировать 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.
Процедуры и функции
Подпрограммы
Процедуры и функции аналогичны программам в миниатюре и имеют общее название – подпрограммы (п/п). Применение п/п дает возможность:
· уменьшить число повторений одной и той же последовательности операторов;
· конструировать программу как совокупность отдельных блоков.
|
|
|
|
|
|
 |
Достоинством нисходящего программирования (разбивка программ на блоки) является повышение надежности программы, т.к. отдельный блок можно программировать и тестировать отдельно от других блоков.
В программе описание процедур и функций должно располагаться в разделе объявлений программы. Каждая подпрограмма определяется один раз, но может быть использована многократно. Структура подпрограммы аналогична структуре полной программы на языке Т-П, но заканчивается END;.
Описать блок значит указать его заголовок и тело:
PROCEDURE A;
В заголовке указываются имя блока и формальные параметры, если таковые есть. Тело блока подобно телу любой программы.