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

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

Линейная сортировка (сортировка отбором)

Идея линейной сортировки по невозрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д.

Приведём пример программы линейной сортировки массива в QBASIC:

REM линейная сортировка

CLS

INPUT "Введите размер массива"; razmer

razmer = razmer - 1

DIM Massiv(razmer)

PRINT "Введите числа в массив"

FOR i = 0 TO razmer

INPUT Massiv(i)

NEXT i

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

max = Massiv(0)

nomer = 0

DO

FOR i = nomer TO razmer

IF Massiv(i) > max THEN

Massiv(nomer) = Massiv(i)

Massiv(i) = max

max = Massiv(nomer)

END IF

NEXT i

nomer = nomer + 1

max = Massiv(nomer)

LOOP WHILE nomer < razmer

PRINT "Максимальное число"; Massiv(0)

FOR i = 0 TO razmer

PRINT Massiv(i);

NEXT i

END

Для запуска программы на исполнение необходимо в меню выбрать RUN => Start или использовать сочетание клавиш Shift F5.

Работает эта конструкция следующим образом. В начале оператор CLS очищает экран. Затем выполняется оператор INPUT с помощью которого устанавливается количество ячеек в массиве. Т.к. все элементы в массиве нумеруются, начиная с ноля, то необходимо учесть это при установлении размера нашего массива уменьшив число размера на 1 в переменной razmer.

Следующий шаг это объявление массива и установление его размера оператором DIM. После выводится сообщение «Введите числа в массив» и при помощи операторов цикла заполняются с клавиатуры все ячейки нашего массива.

Сама сортировка начинается с присвоения переменной max значение первого элемента нашего массива и переменной nomer её порядковый номер в массиве.

Используя цикл с неизвестным числом повторений DO, LOOP WHILE, будем просматривать каждый элемент массива, и сравнивать его с первым элементом просматриваемого участка. Размер просматриваемого участка определяется операторами FOR, TO.

Присваиваем переменной i значение переменной nomer для определения начала анализируемого участка, конец этого участка определяется переменной razmer

Затем проверяется условие, если очередное значение Massiv(i) больше значения переменной max, то производим обмен значениями из первого элемента нашего проверяемого участка и текущего проверяемого значения массива. Такую операцию будем проделывать до тех пор пока не будут сравнены все значения массива между собой.

Увеличение значения nomer на одну единицу позволяет каждый раз уменьшать размер просматриваемого участка массива.

В конце выводим максимальное значение массива, а также все его значения в строку.