Лекция 22.Одномерные массивы. Сортировка одномерного массива.
автор: Садовский Ефим Моисеевич1. Повторение.
Одномерные массивы. Описание. Ввод и вывод. Поиск максимального и минимального элемента массива.
2. Одномерный массив. Сортировка одномерного массива.
Отсортировать одномерный массив – это упорядочить его элементы по возрастанию или убыванию.
Сортировать массив можно различными способами. Давайте рассмотрим один из них, наверное, наиболее простой для понимания.
Например, надо отсортировать целочисленный массив по убыванию.
Пусть исходный массив, например: 5, 3, 1, 7, 9, 4, 5, 8, 7, 5
Сначала найдем максимальный элемент и его порядковый номер.
Максимальный элемент – 9 (на 5 месте).
Ставим его на первое место, но, чтобы не потерять первый элемент, переставляем его на место максимального. То есть меняем максимальный с первым местами.
Получим массив: 9, 3, 1, 7, 5, 4, 5, 8, 7, 5
Определяем максимальный элементов из элементов от второго до последнего. Этот максимальный меняем местами со вторым элементом массива.
Получим: 9, 8, 1, 7, 5, 4, 5, 3, 7, 5
Ищем максимальный из оставшихся, меняем его местами с третьим и т.д.
Выполнив N-1 замену (так как при N-1-й замене последний элемент станет на свое место автоматически, то есть массив будет отсортирован.)
Для сортировки массива сначала оформим задачу поиска максимального элемента массива и перестановки его с первым элементом.
program sort;
var a:array[1..50] of integer;
f,n,i,max,k:integer;
begin
{Ввод массива}
write('Введите количество элементов массива: ')
readln(n);
for i:=1 to n do
begin
write('A[',i,']=');
readln(a[i]);
end;
{Поиск максимального и его порядкового номера}
max:=a[1];
k:=1;
for i:=2 to n do
if a[i]>max then
begin
max:=a[i];
k:=i;
end;
{Перестановка первого элемента и максимального}
f:=a[1];
a[1]:=a[k];
a[k]:=f;
{Вывод массива на экран }
for i:=1 to n do
write(a[i],' ');
writeln;
end.
Такие действия надо выполнить, как мы говорили раньше, N-1 раз.
Добавляем внешний цикл For (по переменной t).
program sort;
var a:array[1..50] of integer;
t,f,n,i,max,k:integer;
begin
{Ввод массива}
write('Введите количество элементов массива: ')
readln(n);
for i:=1 to n do
begin
write('A[',i,']=');
readln(a[i]);
end;
{Поиск максимального и его порядкового номера}
for t:=1 to n-1 do
begin
max:=a[1];
k:=1;
for i:=2 to n do
if a[i]>max then
begin
max:=a[i];
k:=i;
end;
{Перестановка первого элемента и максимального}
f:=a[1];
a[1]:=a[k];
a[k]:=f;
end;
{Вывод массива на экран }
for i:=1 to n do
write(a[i],' ');
writeln;
end. Вспоминаем, что на первом шаге цикла мы сначала за максимальный берем первый элемент, на втором – второй, на третьем – третий и т. д. Аналогично на первом шаге мы максимальный меняем местами с первым, на втором – со вторым и т.д.
Поэтому просто заменяем цифру 1 на переменную t, а число 2 в строке For на t+1.
Получим:
program sort;
var a:array[1..50] of integer;
t,f,n,i,max,k:integer;
begin
{Ввод массива}
write('Введите количество элементов массива: ')
readln(n);
for i:=1 to n do
begin
write('A[',i,']=');
readln(a[i]);
end;
{Сортировка}
for t:=1 to n-1 do
begin
max:=a[t];
k:=t;
for i:=t+1 to n do
if a[i]>max then
begin
max:=a[i];
k:=i;
end;
f:=a[t];
a[t]:=a[k];
a[k]:=f;
end;
{Вывод массива на экран }
for i:=1 to n do
write(a[i],' ');
writeln;
end. Программа сортировки готова.
Для сортировки массива по возрастанию достаточно поменять в условии знак > на знак <.
3. Задачи.
1. Заполнить одномерный массив из 20 элементов случайными числами от 1 до 50. Отсортировать массив по возрастанию.
2. Одномерный массив заполнен целыми числами. Отсортируйте его по убыванию. Затем выведите на экран максимальный и минимальный элементы.
3. Заполнить одномерный массив из n элементов случайными числами от 1 до 30. Отсортировать массив по возрастанию. Вывести на экран число, расположенное в середине, если количество элементов нечетное или фразу "Числа в центре нет", если четное.
Решение задач.
|
