Практическое задание N 2. 33

1. Определить массив из 100 целых случайных чисел в диапазоне от 10 до 1000. Отсортировать массив по убыванию значений элементов методом обмена с использованием оператора цикла с параметром и оператора цикла с условием.

2. Определить массив из 50 вещественных чисел: x[i] = Cos(i/10), i= 1, 2,... 50. Отсортировать массив по убыванию значений элементов методом выбора и вставки.

3. Определить массив из 70 вещественных чисел: x[i]= i*Sin(i/20), i= 1, 2,... 70. Отсортировать массив по возрастанию значений элементов методом вставки и обмена с использованием оператора цикла с условием.

Примечание: составить процедуры сортировки. Подсчитать число перестановок элементов массива и число логических операций в каждом случае. Вывести на экран исходный и отсортированный массивы в виде таблиц чисел с точностью 5 знаков после запятой.

Рассмотрим задачу сортировки таблицы по некоторому ключу (колонке с упорядоченными данными). Например, исходная таблица содержит колонки: фамилия, имя, отчество, средний балл учащихся. Требуется провести сортировку таблицы по ключу (колонке) - "средний балл". При перестановке данных в одной колонке необходимо соответственно переставлять данные в других колонках, т. е. сохранять взаимное расположение данных в каждой строке таблицы. Для этого можно в программу сортировки включить операторы перестановки элементов всех массивов (колонок) параллельно с перестановкой элементов ключевого массива. Однако при этом программы сортировки теряют универсальность. Другой способ сортировки таблицы состоит в определении соответствия между новой и старой нумерацией элементов в ключе (сортируемом массиве "X"). Введем массив "Ne", элементы которого хранят значения индексов в исходном массиве числовых данных. Очевидно, что до сортировки массива "X" Ne[i]:=i; При перестановке элементов массива "X" параллельно необходимо переставлять элементы массива "Ne", например, при сортировке выбором: Nm:= Ne[k]; Ne[k]:= Ne[m]; Ne[m]:= Nm; Новое значения элемента Ne[m] показывает в какой строчке исходной таблицы находился элемент, имеющий в новой таблице индекс "m". Рассмотрим пример.

i 1 2 3 4 5 Индексы исходного массива

x[i] 3.1 2.2 4.7 4.3 3.8 Исходное расположение элементов ключевого массива

x[i] 2.2 3.1 3.8 4.3 4.7 Упорядоченное расположение элементов массива "X"

F[i] 5.5 4.3 7.7 2.1 8.8 Исходное расположение элементов массива "F"

F[Ne[i]] 4.3 5.5 8.8 2.1 7.7 Элементы массива "F" при сортировке по ключу "x"

Ne[i] 2 1 5 4 3 Элементы массива "Ne" при сортировке по ключу "x"

Таким образом, после сортировки по ключу "x" вывод другого массива "F" (колонки) таблицы нужно проводить в цикле: for i:= 1 to N do Writeln(F [ Ne [ i ] ]); После сортировки таблицы вместо массива "F" можно использовать новый массив, например "Fc", элементы которого равны: Fc[i]:=F[Ne[i]]; i=1, 2,... N.

Сортировка может производиться для символьных и строковых данных. Символы сравниваются по номеру ASCII кода, а при сортировке строковых данных сравниваются первые символы строк, затем вторые и т. д. Символы, отсортированные по возрастанию ASCII кода, располагаются в алфавитном порядке. Программы сортировки остаются в прежнем виде, но операторы работают с элементами символьного или строкового типа.