Сортировкаодномерного массива

Устный опрос:
Как описать числовой массив в программе? Назовите основные числовые типы.
Как описать массив строковых переменных в программе?
Как осуществить ввод массива с клавиатуры?
Как осуществить ввод массива с помощью оператора случайных чисел?

Понятие «Сортировка»
Сортировка – один из наиболее распространенных процессов обработки данных.
Сортировкой числового массива называют расположение его элементов в возрастающем или убывающем по величине порядке.
Сортировка символьного массива заключается в расположении элементов, например, по алфавиту или по длине строк. Сортировка массивов включена в качестве стандартной операции во многие системы прикладного обеспечения (MS Word, MS Excel и др).
Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием.
Существует достаточно много методов (алгоритмов) сортировки массивов. Мы рассмотрим два из них: метод прямого выбора и метод обмена (метод “пузырька”)

Метод прямого выбора
Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:
Просматривая массив с первого и до последнего элемента, найти минимальный и поменять его местами с первым элементом.
Просматривая массив со второго и до последнего элемента, найти минимальный и поменять его местами со вторым элементом.
И, так далее, до последнего элемента.

Пример работы алгоритма:
Исходный массив: 8, 3, 6, 1, 4
( меняются местами 8 и 1)
После первого шага: 1, 3, 6, 8, 4
( меняются местами 3 и 3)
После второго шага: 1, 3, 6, 8, 4
(меняются местами 6 и 4)
После третьего шага: 1, 3, 4, 8, 6
(меняются местами 8 и 6)
После четвертого шага: 1, 3, 4, 6, 8

Метод
прямого
выбора
Program Vibor;
const
SIZE = 5;
var
a: array [1..SIZE] of integer;
i,j,buf,k: integer;
begin
for k:=1 to SIZE do read (a [k]);
for i:=1 to SIZE -1 do
{поиск минимального элемента в части массива от a[i] до a[SIZE]}
begin
min:= i;
for j:= i + 1 to SIZE do
if a [j] < a[min] then min:= j;
{поменяем местами a [min] и a [i]}
buf:= a [i];
a [i]:= a [min];
a [min]:= buf;
end;
{выведем массив}
writeln (‘Массив отсортирован^’);
for k:= 1 to SIZE do write (a [k], ‘ ‘);
readln;
end.

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

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

Пример работы алгоритма простого обмена
Исходный массив: 8, 3, 6, 4, 1 (последовательно меняются местами 8 и 3,8 и 6, 8 и 4, 8 и 1)
После первого шага: 3, 6, 4, 1, 8
(далее последовательно меняются местами 6 и 4, 6 и 1)
После второго шага: 3, 4, 1, 6, 8 (последовательно меняются местами 4 и 1)
После третьего шага: 3, 1, 4, 6, 8 (последовательно меняются местами 3 и 1)
После четвертого шага: 1, 3, 4, 6, 8

Program Obmen;
const
SIZE=5
var
a: array [1..SIZE] of integer;
i,k, buf: integer;
begin
write (‘Введите’,SIZE: 3,’целых в одной строке через пробел’);
for k:= 1 to SIZE do read (a [k]);
for i:= 1 to SIZE - 1do
for k:= 1 to SIZE – i do
if a [k] > a [k + 1] then
begin
{обменяем k-й и (k + 1)-й элементы}
buf:= a [k];
a [k]:= a [k + 1];
a [k + 1]:= buf;
end;
writeln (‘Массив отсортирован.’);
for k:= 1 to SIZE do write (a [k], ‘ ’);
readln;
end.
Метод
обмена

Практическая часть
Задача1. На соревнованиях по прыжкам в длину получен массив результатов b(n). Определить три лучших результата. Массив сформировать с помощью функции RANDOM.
Задача2. Составить программу, которая выполняет сортировку фамилий в исходном массиве по алфавиту.