Упорядочение элементов массива
Задача. Расположить элементы массива А в порядке убывания их значений.
Пусть дан массив а = {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).
Рассмотрим алгоритм обмена местами двух элементов: пусть а1 и а4 нужно поменять местами. Введем новую переменную р для временного хранения а1 (можно а4).
a1 a4 1) p = a1
2) a1 = a4
p 3) a4 = p
В общем виде: an и am
an am 1) p = an
2) an = am
p 3) am = 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
Блок-схема алгоритма: