Практика программирования (Бейсик, Си, Паскаль)
Сортировка больших массивов
Говорят, и это подтверждается многочисленными примерами, что 90% времени работы программы.приходится на так называемые узкие места, занимающие в общем объеме программы не более 10% команд. Поиск таких мест и улучшение их временных характеристик — один из основных методов совершенствования программ.
К числу таких узких мест относятся фрагменты программ, занимающиеся упорядочением достаточно объемной информации, поиском данных в больших массивах и т. п. Ниже приводится описание нескольких довольно популярных методов упорядочения числовых массивов и тексты реализующих их процедур. Схемы программ на Си заимствованы из [12], однако в их тексты внесены небольшие изменения. Желающим познакомиться более подробно с другими методами сортировки и возникающими при этом серьезными математическими проблемами мы рекомендуем книгу Д. Кнута "Искусство программирования для ЭВМ", т. 3.
Пузырьковая сортировка (bubble)
Идея этого метода заключается в сравнении двух соседних элементов массива, в результате которого меньшее число (более легкий пузырек) перемещается на одну позицию влево. Обычно такой просмотр организуют с конца массива и после первого прохода самое маленькое число перемещается на первое место. Затем все повторяется от конца массива до второго элемента и т. д.
Известна и другая разновидность обменной сортировки (bubble1), при которой также сравниваются два соседа и, если хотя бы одна из смежных пар была переставлена, просмотр начинают с самого начала. Так продолжают до тех пор, пока очередной просмотр не закончится без перестановок.
С целью повышения быстродействия программ на Си наиболее активно используемые переменные i и j распределяются в регистровой памяти.
Подпрограмма bubble.bas
SUB BUBBLE(X(),N)
FOR 1=1 TO N-l
FOR J=N-1 TO I STEP -1
IF X(J-l) > X(J) THEN
TMP=X(J-1): X(J-l) =X(J): X(J)=TMP
END IF
NEXT J
NEXT I
END SUB
Подпрограмма bubbiei.bas
SUB BUBBLE1(X(),N) M:Q=0
FOR 1=1 TO N-l
IF X(I-l) > X(I) THEN
TMP=X(I-1): X(I-1)=X(I): X(I)=TMP: Q=l
