Практика программирования (Бейсик, Си, Паскаль)



Сортировка больших массивов


Говорят, и это подтверждается многочисленными примерами, что 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




Содержание  Назад  Вперед