Методы сортировки массивов
ЛАБОРАТОРНАЯ РАБОТА №4
Программирование алгоритмов с разветвляющейся структурой и с циклическими структурами. Массивы
Цель и задача работы: научиться разрабатывать программы обработки массивов с применением операторов цикла.
Массивы
Рассмотренные ранее простые типы данных позволяют использовать в программе одиночные объекты – числа, символы, строки и т.п. В Турбо Паскале могут использоваться также объекты, содержащие множество однотипных элементов. Это массивы – формальное объединение нескольких однотипных объектов (чисел, символов, строк и т.п.), рассматриваемое как единое целое. Массивов используются тогда, когда требуется связать и использовать целый ряд родственных величин. Например, результаты многократных замеров температуры воздуха в течение года удобно рассматривать как совокупность вещественных чисел, объединенных в один сложный объект – массив измерений.
При описании массива необходимо указать общее число входящих в массив элементов и тип этих элементов. Например:
var
a: array [1..10] of real;
b: array[0..50] of integer;
c: array[-3..4] of boolean;
При описании массива используются зарезервированные слова ARRAY и OF (массив, из). За словом ARRAY в квадратных скобках указывается тип-диапазон, с помощью которого компилятор определяет общее число элементов массива. Тип-диапазон задается левой и правой границами изменения индекса массива, так что массив a состоит из 10 элементов, массив b из 51, а массив c – из 8 элементов. За словом OF указывается тип элементов, образующих массив.
Доступ к каждому элементу массива в программе осуществляется с помощью индекса – целого числа (точнее, выражения порядкового типа), служащего своеобразным именем элемента в массиве (если левая граница типа-диапазона равна 1, индекс элемента совпадает с его порядковым номером).
Пример обращения к элементу массива.
b[17] := 123;
c[-2] := a[1]>a[2];
for k := 1 to 10 do a[k] := 0;
В правильно составленной программе индекс не должен выходит за пределы, определенные типом-диапазоном. При обращении к элементу a[0] Турбо Паскаль выдаст ошибку. Турбо Паскаль может контролировать использование индексов в программе на этапе компиляции и на этапе выполнения программы.
Пример
Нахождение максимального, минимального значения в массиве, а также вычисление среднего арифметического значений массива.
const
N = 1000;
MaxValue = 100+1;
var
a: array[1..N] of integer;
i: integer;
max, min: integer;
s: real;
begin
for i := 1 to N do a[i] := random(MaxValue);
s := 0;
max := a[1];
min := a[1];
for i := 1 to N do
begin
s := s+a[i];
if a[i]<min then min := a[i];
if a[i]>max then max := a[i];
end;
writeln( ’Мин = ’, min, ’ Макс = ’, max, ’ Среднее = ’,
s/N );
end.
Для создания массива используется встроенная функция RANDOM(MAX), которая возвращает случайное целое число, равномерно распределенное в диапазоне от 0 до MAX–1 (MAX – передаваемый параметр).
Описание типа (type)
Строго говоря, массив это один из структурированных типов данных Турбо Паскаля. Благодаря предусмотренному в Турбо Паскале механизму создания новых типов, программист может описать свой тип-массив:
type
Vector = array[1..3] of real;
а затем использовать его в разделе описания переменных:
var
a, b: Vector;
Тип идущий за словом OF, – любой тип Турбо Паскаля. Он может быть, в частности и другим массивом:
var
a: array[1..3] of array[–2..2] of array[1..5] of real;
Такую запись можно заменить более компактной:
var
a: array[1..3, –2..2, 1..5] of real;
Глубина вложенности структурированных типов вообще, а, следовательно, и массивов – произвольная, поэтому размерность массива не ограничена.
В Турбо Паскале можно одним оператором присваивания передать все элементы одного массива другому массиву того же типа, например:
var
a, b: Vector;
или
a, b: array[1..5] of real;
...
a := b;
Но!!! Type mismatch
var
a: array[1..5] of real;
b: array[1..5] of real;
...
a := b; {Здесь возникнет ошибка несоответствия типов}
Однако над массивами не определены операции отношения, поэтому сравнить два массива можно только поэлементно.
Пример
var
a, b: array[1..5] of real;
eq: boolean;
i: integer;
...
eq := true;
for i := 1 to 5 do
if a[i]<>b[i] then eq := false;
if eq then ...
Методы сортировки массивов
Часто при решении задач обработки данных возникают задачи упорядочивания множества подобных данных в возрастающем или убывающем порядке (задачи сортировки).
Алгоритмы сортировки хорошо исследованы и изучены. Различные подходы к сортировке обладают различными характеристиками. Хотя некоторые методы в среднем могут быть лучше других, ни один из методов не будет идеальным для всех ситуаций, поэтому каждый программист должен иметь в своем распоряжении несколько различных типов сортировки.