Структура данных - массив. Часть 1 - 26 стр.

UptoLike

Составители:

Рубрика:

3.5. Сортировка массива

Сортировка массива относится к операциям, изменяющим состояние

массива без изменения количества элементов в нем. Остановимся на трех

простых методах: метод вставки (включения), метод выбора и метод обмена

(метод пузырька). Алгоритмы этих методов описаны в [1]. Сложность этих

алгоритмов определяется как O(n

Сортировку будем осуществлять в порядке неубывания элементов мас-

сива, то есть выходной массив должен удовлетворять условию:

(∀i:1≤i<n:a[i]≤a[i+1])

Постановка задачи.

Входные данные

: n − количество элементов массива,

a[1..n] ∈ Z (множеству целых чисел).

Выходные данные

: измененный массив a[1..n].

Промежуточные данные:

i,j– индексы для просмотра элементов массива.

Метод вставки (включения):

1) предполагается, что массив из одного элемента упорядочен;

2) для всех остальных элементов

( 2≤j ≤n) выполнить следующее

действие: вызвать процедуру вставки в упорядоченный массив

Insert(j-1,a,a[j]).

Опишем алгоритм сортировки в виде процедуры Sort_Ins, при-

чем вместо вызова процедуры

Insert(j-1,a,a[j]) подставим ее те-

ло, заменяя формальные параметры на фактические.