Методы сортировки массивов

ЛАБОРАТОРНАЯ РАБОТА №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 ...

Методы сортировки массивов

Часто при решении задач обработки данных возникают задачи упорядочивания множества подобных данных в возрастающем или убывающем порядке (задачи сортировки).

Алгоритмы сортировки хорошо исследованы и изучены. Различные подходы к сортировке обладают различными характеристиками. Хотя некоторые методы в среднем могут быть лучше других, ни один из методов не будет идеальным для всех ситуаций, поэтому каждый программист должен иметь в своем распоряжении несколько различных типов сортировки.