Занятие 4.
Одна из стандартных задач программирования - сортировка элементов массива. Массив - это набор переменных, содержащих элементы одного типа. С массивами вы встречаетесь каждый день не только в программировании, но и в обычной жизни.
Например: все люди, которые вышли утром из своих квартир на улицы - это массив типа люди. Его можно разделить на более мелкие массивы: массив тех, кто идет пешком, массив тех, кто едет на своей машине и массив тех, кто едет общественным транспортом. Последних тоже можно поделить на массивы: массив тех, кто едет трамваем, массив тех, кто едет троллейбусом, массив тех, кто едет автобусом и так далее. Кстати, можем еще рассмотреть массив тех, кто выходит на определенной остановке. Но главное - это то, что все они - люди (тип переменной) и что они куда-то добираются (общая задача).
Нельзя запихнуть в один массив тетрадь по информатике и бутерброд, который мама дала с собой в школу. Они разных типов. :-)
А теперь с переменными. Вот, допустим, у вас есть 20 участников олимпиады по информатике. Надо отсортировать их так, чтоб тот, у кого больше баллов, получил первое место, а тот, у кого меньше всех баллов - последнее.
Да, я знаю, что проще сделать это, например, в Excel. Но, во-первых, мы учимся программировать. А во-вторых - не поверите, но Excel - это программа, которую тоже кто-то когда-то написал!
Давайте, для начала, рассмотрим задачу попроще. Пусть у нас будет какое-то количество чисел, а мы выстроим их в порядке возрастания (от меньшего к большему).
Существует много разных методов сортировки, вы можете почитать о них, например, здесь, но мы будем использовать метод "Пузырька".
Если взять бутылку с шампунем и потрясти ее как следует, то получатся пузырьки. А если бутылку перевернуть, то пузырьки наперегонки полетят вверх. И чем больше будет пузырек, тем быстрее он доберется наверх. Таковы законы физики.
В нашем случае - с числами - будет примерно так же.
Отсортируем такой массив чисел:
81 5 32 47 16 - это наш исходный массив. Теперь, сравнивая два соседних элемента, мы будем менять их местами, если ЛЕВЫЙ окажется больше ПРАВОГО.
- Сравним 81 и 5. Больше 81. Меняем местами. После первого сравнения получим ряд: 5 81 32 47 16
- Сравним 81 и 32. Больше 81. Меняем местами.
- И так до конца ряда. Когда ряд будет пройден до конца, 81 как самое большое число окажется в конце.
5 32 47 16 81
Когда мы пройдем ряд от начала до конца второй раз, массив примет вид:
5 32 16 47 81
После третьего прохода:
5 16 32 47 81
Пройдя по нашему массиву три раза, мы его полностью расставили по порядку. Но так бывает не всегда. Гарантированный результат мы получим, если пройдем по массиву столько раз, сколько в нем элементов.
Есть еще одна проблема, о которой важно знать. Как правильно менять местами два элемента в массиве? Рассмотрим два варианта.
Обмен элементов с введением дополнительной переменной.
Надо поменять местами элементы a и b. Дополнительная переменная - c.
c:=a;
a:=b;
b:=c;
Сразу возникает вопрос - а зачем нам с? Смотрите: пусть a=2, b=3.
Неправильно
|
Правильно
|
||
a=2, b=3
|
a=2, b=3
|
||
a:=b
|
b=3, a=3.
|
c:=a
|
a=2, b=3, c=2
|
b:=a
|
b=3, a=3.
|
a:=b
|
a=3, b=3, c=2
|
Мы потеряли число 2.
|
b:=c
|
a=3, b=2, c=2
|
|
Обмен элементов без введения дополнительной переменной.
a:=a+b;
b:=a-b;
a:=a-b;
b:=a-b;
a:=a-b;
В принципе, можно любым способом, но мне кажется, что первый - надежнее.
А теперь возвращаемся к задаче.
В файле ввода данных содержится неизвестное количество целых чисел, не менее одного, не более 20. В файл вывода данных вывести все эти числа, отсортировав их в порядке возрастания.
Логика решения:
- Нам нужны две переменные типа text для работы с файлами ввода и вывода данных.
- Нам нужен массив для 20 целых чисел (не больше - по условию, но и не меньше - мы не знаем, сколько их будет). Значит, a: array [1.. 20] of integer;
- Нам будут нужны переменные типа integer:
- i - это будет номер элемента в массиве
- j - это будет число проходов по массиву
- k - это будет ячейка для временного хранения значения элемента при обмене
- n - это будет количество элементов в массиве, когда посчитаем.
- Ход решения:
- Считываем все элементы из файла ввода
- Сортируем их методом пузырька
- Выводим в файл вывода
program Sortirovka;
var
a: array[1..20] of integer;
i,j,k,n:integer;
f,g:text;
begin
i:=1;
n:=0;
assign(f,'input.txt');
reset(f);
while not eof (f) do
begin
read (f, a[i]);
i:=i+1;
n:=n+1;
end;
close (f);
For i:=1 to n do
For j:=1 to n-1 do
if a[j]>a[j+1] then begin
k:=a[j];
a[j]:=a[j+1];
a[j+1]:=k;
end;
assign (g,'output.txt');
rewrite (g);
for i:=1 to n do begin
write (g, a[i]:3);
end;
close (g);
end.
Самостоятельная работа:
- Изменить программу так, чтоб она сортировала элементы по убыванию (от большего к меньшему).
- Изменить программу так, чтоб она сортировала не числа, а буквы по алфавиту.
- Изменить программу так, чтобы она сортировала не буквы (один символ) а слова, например, вводят список фамилий и производится сортировка по алфавиту.
- В файле ввода данных список вида: фамилия - балл за олимпиаду. Например:
Петров 65
Сидоров 55
Составить программу, которая выведет в файл вывода данных список фамилий, отсортированный по результатам олимпиады:
Петров 65
Иванов 60
Сидоров 55
