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

Сортировкой является такая перестановка элементов (в массиве), после которой они оказываются упорядоченными требуемым образом.

5.2.1. Сортировка методом пузырька

Этот метод основан на попарном сравнении смежных элементов данных; если порядок следования элементов в очередной паре неправилен, то эти элементы обмениваются местами. Для выполнения обмена требуется дополнительная переменная, сохраняющая на время обмена одно из значений. Если значения, которыми надо обменяться, содержатся в переменных А и В, то обмен можно выполнить посредством операторов

Т=А

А=В

В=Т

использующих переменную Т (в качестве рабочей ячейки). Обмен значениями строковых переменных осуществляется аналогичным образом.

Обсудим сортировку числовых значений в порядке убывания. Применение метода пузырька к массиву с размером 4 иллюстрирует рисунок.

Массив А

А(1)	А(2)	А(3)	А(4)
7	14	-2	26	Начальное содержимое
<——Пробегаемые значения——>
14	7	26	-2	После первого прохода
<Пробегаемые значения->
14	26	7	-2	После второго прохода
<Пробегаемые значения>
26	14	7	-2	После заключительного, третьего прохода

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

REM ФРАГМЕНТ ПРОГРАММЫ ПУЗЫРЬКОВОЙ СОРТИРОВКИ

REM ПРЕДПОЛАГАЕТСЯ, ЧТО ЗНАЧЕНИЯ СОДЕРЖАТСЯ

REM В МАССИВЕ А(1), .... A(N) И СОРТИРУЮТСЯ

REM В ПОРЯДКЕ УБЫВАНИЯ

FOR I=N TO 2 STEP -1

FOR J=l TO I-1

IF A(J)<A(J+1) THEN

T=A(J)

A(J)=A(J+1)

A(J+1)=T

END IF

NEXT J

NEXT I

REM КОНЕЦ СОРТИРОВКИ

5.2.2. Сортировка массива с помощью оператора обмена swap

Оператор SWAP осуществляет обмен значениями между двумя переменными. Он оказывается полезным при составлении программ сортировки числовых и символьных массивов.

Формат записи оператора:

SWAP имя-переменной-1, имя-переменной-2

В результате выполнения оператора переменной-1 присваивается значение переменной-2, а переменной-2 присваивается значение переменной-1. Обе переменные должны быть одного типа, в противном случае система выдает сообщение об ошибке 13

НЕСООТВЕТСТВИЕ ТИПОВ В СТРОКЕ n

Пример. Отсортировать одномерный массив в порядке возрастания значений.

INPUT "Введите размерность массива N="; N

DIM A(N)

FOR I = 1 TO N

PRINT "A("; I; ")"

INPUT A(I)

NEXT I

FOR I =1 TO N-1

FOR J =I+1 TO N

IF A(I) > A(J) THEN

SWAP A(I), A(J)

END IF

NEXT J, I

FOR I = 1 TO N

PRINT A(I);

NEXT I

PRINT

END