Упорядочение элементов массива

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

Пусть дан массив а = {3, 2, -1, 10, 0, 5}, i = 1,…,6.

Должны получить

Рассмотрим алгоритм на примере:

1). Ищем максимальный элемент в массиве и ставим его на 1-е место, поменяв местами 1-ый и максимальный:

3 2 –1 10 0 5 Þ 10 2 –1 3 0 5

2). Ищем максимальный элемент среди элементов со 2-го по 6-й и ставим его на 2-е место, поменяв местами со 2-м элементов:

10 2 –1 3 0 5 Þ 10 5 –1 3 0 2

3). Ищем максимальный элемент среди элементов с 3-го по 6-й и ставим его на 3-е место.

10 5 –1 3 0 2 Þ 10 5 3 –1 0 2

4). Далее – аналогично:

10 5 3-1 0 2 Þ 10 5 3 2 0 -1

5). 10 5 3 2 0 –1 Þ 10 5 3 2 0 –1

После этого 5-го шага на последнем месте оказывается минимальный элемент, получен упорядоченный массив.

Просматривать и искать максимальный элемент нужно (n-1) раз (у нас 5 раз при n = 6).

Рассмотрим алгоритм обмена местами двух элементов: пусть а₁ и а₄ нужно поменять местами. Введем новую переменную р для временного хранения а₁ (можно а₄).

a₁ a₄ 1) p = a₁

2) a₁ = a₄

p 3) a₄ = p

В общем виде: a_n и a_m

a_n a_m 1) p = a_n

2) a_n = a_m

p 3) a_m = p

Фрагмент программного кода:

For k = 1 to 5

imax = k ‘считаем k-ый элемент максимальным

for i = k to 6 ‘поиск максимального элемента

if a(i) > a (imax) then imax = i ‘среди элементов c

next i ‘k – ого по 6-й

p = a(k) ‘меняем местами

a(k) = a(imax) ‘k-ый элемент и

a(imax) = p ‘найденный максимальный

next k

for i = 1 to 6

Picture2.Print a(i); Spc(2);

Next i

Блок-схема алгоритма:

Дата добавления: 2014-01-07