Другие методы сортировки

 

Сортировка Шелла быстрее метода пузырька, она похожа на метод пузырька, но, в отличие от него, начинает сравнивать не смежные, а далеко отстоящие друг от друга значения (примерно на N/2) и сортирует все эти значения, а затем уменьшает расстояние между сравниваемыми значениями. На последнем проходе расстояние между ними равно 1 и поэтому фактически этот проход выполняется по методу пузырька.

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

Если нам требуется отсортировать массив А(100), то надо ввести индекс I(100), лучше всего целочисленный, если такая возможность предусмотрена в системе (это сократит занимаемую массивом память), и задать начальные значения его элементов операторами

FOR L=0 TO 100

I(L) =L

NEXT L

Для индекса должно выполняться соотношение

I(исходная позиция) = новая позиция

поэтому перед началом сортировки I(1) = 1, I(2) = 2 и т. д. При сортировке во время каждого прохода сравниваются значения изА, определенные по I(), а переставляются значения индекса в I().

При введении индекса программа для сортировки методом пузырькапревратится в следующую программу:

REM СОРТИРОВКА С ПРИМЕНЕНИЕМ ИНДЕКСА

FOR L=l TO N

I(L)=L

NEXT L

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

REM

FOR I=N TO 2 STEP –1

FOR J=l TO I-1

I1=I(J)

I2=I(J+1)

IF A(I1)<A(I2) THEN

I(J)=I2

I(J+1)=I1

ENDIF

NEXT J

NEXT I

REM КОНЕЦ СОРТИРОВКИ С ПРИМЕНЕНИЕМ ИНДЕКСА

Операторы

FOR L = 1 ТО N

PRINT A (L);

NEXT L

распечатают исходный, неизмененный набор значений, а операторы

FOR L = 1 ТО N

I1=I(L)

PRINT A(II)

NEXT L

распечатают отсортированный набор значений.

Пример. Задана целочисленная квадратная матрица. Необходимо упорядочить элементы главной диагонали матрицы по убыванию.

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

DIM A(N, N)

FOR I = 1 TO N

FOR J = 1 TO N

PRINT " A("; I; J; ")=";

INPUT A(I, J)

NEXT J, I

FOR I = 1 TO N - 1

FOR J = I + 1 TO N

IF A(I, I) < A(J, J) THEN

SWAP A(I, I), A(J, J)

END IF

NEXT J, I

FOR I = 1 TO N

FOR J = 1 TO N

PRINT A(I, J);

NEXT J

PRINT

NEXT I

END