Занятие 4. Поговорим о сортировке.

Занятие 4.

Одна из стандартных задач программирования - сортировка элементов массива. Массив - это набор переменных, содержащих элементы одного типа. С массивами вы встречаетесь каждый день не только в программировании, но и в обычной жизни.

Например: все люди, которые вышли утром из своих квартир на улицы - это массив типа люди. Его можно разделить на более мелкие массивы: массив тех, кто идет пешком, массив тех, кто едет на своей машине и массив тех, кто едет общественным транспортом. Последних тоже можно поделить на массивы: массив тех, кто едет трамваем, массив тех, кто едет троллейбусом, массив тех, кто едет автобусом и так далее. Кстати, можем еще рассмотреть массив тех, кто выходит на определенной остановке. Но главное - это то, что все они - люди (тип переменной) и что они куда-то добираются (общая задача).

Нельзя запихнуть в один массив тетрадь по информатике и бутерброд, который мама дала с собой в школу. Они разных типов. :-)

А теперь с переменными. Вот, допустим, у вас есть 20 участников олимпиады по информатике. Надо отсортировать их так, чтоб тот, у кого больше баллов, получил первое место, а тот, у кого меньше всех баллов - последнее. 

Да, я знаю, что проще сделать это, например, в Excel. Но, во-первых, мы учимся программировать. А во-вторых - не поверите, но Excel - это программа, которую тоже кто-то когда-то написал!

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

Существует много разных методов сортировки, вы можете почитать о них, например, здесь, но мы будем использовать метод "Пузырька".

Если взять бутылку с шампунем и потрясти ее как следует, то получатся пузырьки. А если бутылку перевернуть, то пузырьки наперегонки полетят вверх. И чем больше будет пузырек, тем быстрее он доберется наверх. Таковы законы физики.

В нашем случае - с числами - будет примерно так же.

Отсортируем такой массив чисел: 

81  5  32  47  16  - это наш исходный массив. Теперь, сравнивая два соседних элемента, мы будем менять их местами, если ЛЕВЫЙ окажется больше ПРАВОГО.

1. Сравним 81 и 5. Больше 81. Меняем местами. После первого сравнения получим ряд:   5 81 32 47 16
2. Сравним 81 и 32. Больше 81. Меняем местами. 
3. И так до конца ряда. Когда ряд будет пройден до конца, 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;

В принципе, можно любым способом, но мне кажется, что первый - надежнее.

А теперь возвращаемся к задаче.

В файле ввода данных содержится неизвестное количество целых чисел, не менее одного, не более 20. В файл вывода данных вывести все эти числа, отсортировав их в порядке возрастания.

Логика решения:

1. Нам нужны две переменные типа text для работы с файлами ввода и вывода данных.
2. Нам нужен массив для 20 целых чисел (не больше - по условию, но и не меньше - мы не знаем, сколько их будет). Значит, a: array [1.. 20] of integer;
3. Нам будут нужны переменные типа  integer:
• i - это будет номер элемента в массиве
• j - это будет число проходов по массиву
• k - это будет ячейка для временного хранения значения элемента при обмене
• n - это будет количество элементов в массиве, когда посчитаем.
4. Ход решения: 
• Считываем все элементы из файла ввода
• Сортируем их методом пузырька
• Выводим в файл вывода

Текст программы:

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.

Самостоятельная работа:

1. Изменить программу так, чтоб она сортировала элементы по убыванию (от большего к меньшему).
2. Изменить программу так, чтоб она сортировала не числа, а буквы по алфавиту.
3. Изменить программу так, чтобы она сортировала не буквы (один символ) а слова, например, вводят список фамилий и производится сортировка по алфавиту.
4. В файле ввода данных список вида: фамилия - балл за олимпиаду. Например:

Иванов 60
Петров 65
Сидоров 55

Составить программу, которая выведет в файл вывода данных список фамилий, отсортированный по результатам олимпиады:

Петров 65
Иванов 60
Сидоров 55