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

Date: 2015-10-07; view: 361.

Классической задачей по обработке массивов является задача упорядочения (сортировки): расположить значения элементов массива в порядке их возрастания или убывания.

Продумано много алгоритмов ее решения, каждый из которых может оказаться наиболее выгодным в зависимости от особенностей данного массива. Если, например, дан большой массив из цифр, то для его упорядочения нет нужды многократно сравнивать и переставлять элементы, достаточно подсчитать количество каждой цифры и в соответствии с этим сформировать массив. Но совсем неуклюже будет выглядеть работа программы по этому алгоритму на массиве, не имеющем одинаковых элементов. Здесь более выгодно применить метод, основанный на нахождении максимального (минимального) элемента массива: находим максимальный (минимальный) элемент и меняем его местами с последним (первым), из оставшихся опять находим максимальный (минимальный) и меняем его с предпоследним (вторым) и так далее.

Пример: сортировка массива по возрастанию.

Дано: А(n) – одномерный массив размерности n.

Результат: A(n) – массив упорядоченный по возрастанию

Используемые переменные: Р – переменная для хранения промежуточного значения минимального элемента, К – индекс минимального элемента, I – индекс элемента упорядоченного массива – управляющая переменная внешнего цикла, J – индекс элемента части массива в которой ищется минимальный элемент – управляющая переменная внутреннего цикла.

CLS

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

DIM A(N)

FOR I=0 TO 9

A(I)=INT(RND*200)-100

? A(I);

NEXT I

FOR I=0 TO N-1

P=A(I):K=I

FOR J=I+1 TO N

IF A(J)>=P THEN 5

P=A(J):K=J

5 NEXT J

A(K)=A(I): A(I)=P

NEXT I

FOR I=0 TO N

? A(I);

NEXT I

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

Пример: сортировка массива пузырьковым способом.

Дано: массив М(9)

Результат: упорядоченный по возрастанию массив М(9)

Используемые переменные: D – дополнительная переменная для хранения элемента массива при смене его с соседним, S – переменная которая является признаком завершения сортировки, если S=1, то происходит перестановка, если S=0, то замен больше не происходит.

DIM M(9)

FOR I=0 TO 9

A(I)=INT(RND*200)-100

? A(I);

NEXT I

10 S=0

FOR I=0 TO 8

IF M(I)<=M(I+1) THEN 20

D=M(I)

M(I)=M(I+1)

M(I+1)=D

S=1

20 NEXT I

IF S=1 THEN 10

FOR I=0 TO 9

? M(I);

NEXT I

Метод пузырьковой сортировки в настоящее время представляет лишь исторический интерес и в практическом программировании, по-видимому, не используется, так как разработаны значительно более эффективные способы "быстрой" сортировки любых массивов.