Массивы. Сортировка элементов массива.

Массив представляет собой совокупность данных одного типа с общим для всех элементов именем. Элементы массива пронумерованы, и обратиться к каждому из них можно, указав его индекс (для одномерного массива) или несколько индексов (для многомерных массивов). В программировании количество индексов массива называют его размерностью.

Массив относится к группе структурных типов и описывается в разделе описания переменных в следующей форме:

Var <идентификатор >: А rrау [<тп индекса>] Of <mun компонент>;

Тип индекса может быть любым скалярным порядковым типом, кроме longint. Чаще всего в качестве типа индекса употребляется интервальный тип. Например, одномерный массив А, состоящий из 12 вещественных чисел опишется следующим образом:

Var А: аггау [1..12] Of Real;

Описание массива определяет, во-первых, размещение массива в памяти, во-вторых, правила его дальнейшего употребления в программе. Последовательные элементы массива располагаются в последовательных ячейках памяти (А[ 1 ], А[ 2 ] и т. д.), причем значения индекса не должны выходить из диапазона 1.. 12. В качестве индекса может употребляться любое выражение соответствующего типа. Например, A [i+j], A [m div 2].

Например, в программе могут присутствовать следующие описания: Var Cod: array [Char] Of 1..100;

L: array [Boolean] Of Char;

В такой программе допустимы следующие обозначения элементов массивов:

Cod ['х']; L[true]; Cod[chr(65)]; L[a>0];

Алгоритмы сортировки элементов массива.

Под сортировкой массива подразумевается процесс перестановки Элементов с целью упорядочивания их в соответствии с каким-либо критерием. Например, если имеется массив целых а, то после сортировки по возрастанию должно выполниться условие:

а'₁,≤ а'₂ ≤,...,≤ а'_п

Так как можно сравнивать переменные типов INTEGER, REAL, CHAR и STRING, то можно сортировать массивы этих типов.

Задача сортировки распространена в информационных системах и используется как предварительный этап задачи поиска, так как поиск в упорядоченном (отсортированном) массиве проводится намного быстрее, чем в неупорядоченном.

Существует много методов (алгоритмов) сортировки массивов. Рассмотрим два метода:

· метод прямого выбора

· метод прямого обмена

1). Сортировка выбором.

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

Program Sort_Vybor;

Const

size=5;

Var

a: array[1.. size ] of integer;

i: integer; { номер элемента, от которого ведется поиск мин. эл-та. }

min: integer; { номер минимального элемента }

j: integer; { номер элемента, сравниваемого с минимальным }

buf: integer; { буфер, используемый при обмене элементов массива }

k: integer;

Begin

writeln (′Сортировка массива.′);

write (′Введите′ ֽ size:3 ֽ′ целых в одной строке ′);

writeln (′через пробел и нажмите <Enter>′);

for k:=1 to size do read (a [k]);

writeln (′Сортировка ′);

for i:=1 to size-1 do

Begin

{ поиск мин. элемента в части массива от a(i) до a(size) }

min:=I;

for j:=i+1 to size do begin

if a[j]< a[min] then min:=j;

{ поменяем местами a[min] и a[i] }

buf:= a[i];

a[i]:= a[min];

a[min]:= buf;

{ выведем массив }

for k:=1 to size do write(a[k], ′ ′);

writelen;

End;

End;

writeln (′ Массив отсортирован. ′);

End.

2). Сортировка обменом (методом "пузырька")

В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут), поэтому этот метод иногда называют "пузырьковым". Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.

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

Program Sort;

Const

size=5;

Var

a: array[1.. size ] of integer;

i: integer; { счетчик циклов }

k: integer; { текущий индекс элемента массива }

buf: integer;

Begin

writeln (′Сортировка массива пузырьковым методом.′);

write (′Введите′ ֽ size:3 ֽ′ целых в одной строке ′);

writeln (′через пробел и нажмите <Enter>′);

for k:=1 to size do read (a [k]);

writeln (′Сортировка ′);

for i:=1 to size-1

do Begin

for k:=1 to size-1

do begin

if a[k]> a[k+1]

then begin

{ поменяем местами a[k] и a[k+1] }

buf:= a[k];

a[k]:= a[k+1];

a[k+1]:= buf;

End;

End;

for k:=1 to size do write(a[k], ′ ′);

writelen;

End;

writeln (′ Массив отсортирован. ′);

End.

Не нашли, что искали? Воспользуйтесь поиском: