Сортировка одномерного массива методом простого выбора

На каждом шаге находится минимальный (максимальный) неотсортированной части. Он меняется с первым элементом в неотсортированной части, после чего отсортированная часть увеличивается на один элемент. На первом шаге весь массив считается неотсортированным. Сортировка заканчивается за (n-1) шаг

 

Сортировка одномерного массива пузырьковым методом

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

 

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

Говорят, и это подтверждается многочисленными примерами, что 90% времени работы программы.приходится на так называемые узкие места, занимающие в общем объеме программы не более 10% команд. Поиск таких мест и улучшение их временных характеристик - один из основных методов совершенствования программ.

К числу таких узких мест относятся фрагменты программ, занимающиеся упорядочением достаточно объемной информации, поиском данных в больших массивах и т. п. Ниже приводится описание нескольких довольно популярных методов упорядочения числовых массивов и тексты реализующих их процедур. Желающим познакомиться более подробно с другими методами сортировки и возникающими при этом серьезными математическими проблемами мы рекомендуем книгу Д. Кнута "Искусство программирования для ЭВМ", т. 3.

Пузырьковая сортировка

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

Известна и другая разновидность обменной сортировки (bubble1), при которой также сравниваются два соседа и, если хотя бы одна из смежных пар была переставлена, просмотр начинают с самого начала. Так продолжают до тех пор, пока очередной просмотр не закончится без перестановок.

   Подпрограмма 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

END IF

NEXT I

IF Q=l THEN GOTO *M

END SUB

Сортировка методом отбора

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

Подпрограмма select.bas

SUB SELECT(X(),N)

FOR I=0 TO N-2

Q=0: K=I: TMP=X(I)

FOR J=I+1 TO N-l

IF X(J)<="" pre="">

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

Идея этого метода базируется на последовательном пополнении ранее упорядоченных элементов. На первом шаге сортируются первые два элемента. Затем на свое место среди них вставляется третий элемент. К трем упорядоченным элементам добавляется четвертый, который занимает свое место в новой четверке. И так продолжается до тех пор, пока к n-1 ранее упорядоченным элементам не присоединится последний. Примерно таким способом игроки упорядочивают свои карты при сдаче их по одной.

Подпрограмма insert.bas

SUB INSERT(X%(),N%) DIM I,J,TMP

FOR I=1 TO N-l TMP=X(I)

FOR J=I-1 TO 0 STEP -1

IF TMP > X(J) THEN EXIT FOR

X(J+1)=X(J)

NEXT В X(J+1)=TMP

NEXT I

END SUB

Сортировка методом Шелла

Метод Д. Л. Шелла, опубликованный в 1959 г., предлагает сортировать массив в несколько этапов. На первом этапе в сортировке участвуют достаточно далекие элементы, например, отстоящие друг от друга на восемь позиций. На втором проходе сортируются элементы, расстояние между которыми уменьшено, например до четырех. Затем упорядочиваются каждые вторые элементы и, наконец, на последнем этапе сравниваются смежные элементы. Выбор последовательно уменьшающихся шагов в методе Шелла представляет довольно сложную математическую задачу. На практике чаще всего применяют пятизвенную схему 9->5->3->2->1.

Подпрограмма shell.bas

SUB SHELLSORT (X%"(), N%)

DIM I, J,GAP,K,XX,A(5) A(0)=9: A(l)=5: A(2)=3: A(3)=2: A(4)=l

FOR K=0 TO 4 GAP=A(K)

FOR I=GAP TO N-1 XX=X(I)

FOR J=I-GAP TO 0 STEP -GAP

IF XX >= X(J) THEN EXIT FOR

X(J+GAP)=X(J)

NEXT J X(J+GAP)=XX: NEXT I: NEXT К: END SUB

Сортировка методом Хоара

Один из самых лучших алгоритмов сортировки - быстрая сортировка (quicksort), которая была придумана в 1960 году Чарльзом Хоаром (С. A. R. Ноаге). Быстрая сортировка - замечательный пример того, как можно избежать лишних вычислений. Она работает при помощи разделения массива на большие и маленькие элементы:

Quicksort

• выбрать один элемент массива ("разделитель"):
• разбить оставшиеся элементы на две группы:
• "маленькие", то есть меньшие, чем разделитель,
• "большие", то есть большие или равные разделителю,
• рекурсивно отсортировать обе группы.

Когда этот процесс закончится, то массив будет отсортирован. Быстрая сортировка работает быстро, потому что, как только мы узнаем, что элемент меньше, чем разделитель, нам уже не нужно его сравнивать с большими элементами; аналогично, большие элементы не сравниваются с маленькими. Поэтому данный алгоритм существенно быстрее, чем такие простые методы сортировки, как сортировка вставкой или пузырьком, когда каждый элемент сравнивается напрямую со всеми остальными.
Метод Ч. Э. Р. Хоара, опубликованный в 1962 г., издалека напоминает способ ловли льва в пустыне "методом Вейерштрасса". Сначала пустыню делят пополам и выбирают ту половину, в которой находится лев. Затем эту половину снова делят пополам и так продолжают до тех пор, пока область, содержащая льва, не помещается в клетку. В математике подобный метод применяют для нахождения корня функции, принимающей на концах отрезка разные знаки. Это и есть метод Вейерштрасса, более известный под названием "метода деления пополам".
Хоар применил подобный подход к сортировке и предложил следующий алгоритм. Выберем какой-то средний элемент последовательности хх (обычно в качестве такового выбирают средний элемент). Если он стоит на своем месте (имеется в виду ситуация, когда последовательность упорядочена), то все элементы, расположенные левее, не больше хх, а элементы, находящиеся правее, - не меньше хх. Поэтому первый шаг быстрой сортировки заключается в том, чтобы перенести в левую часть массива те элементы правой половины, которые меньше хх, а в правую часть - те элементы из левой половины, которые больше хх. Обычно при этом поиск ведут в обе стороны от хх и как только обнаруживают пару, нарушающую порядок, производят обмен.
Затем аналогичный прием применяют к каждой из полученных половин. В каждой из них выбирается свой средний элемент и относительно него осуществляются необходимые перестановки. Как следует из описания, алгоритм Хоара очень хорошо укладывается в понятие рекурсивной процедуры. Для единообразия в обращении процедура быстрой сортировки представлена в виде двух процедур - внешней hoar, к которой обращается пользователь, и внутренней - quick. Последняя выполняет рекурсивную обработку подмассива, заданного граничными значениями индексов - left и right.

Подпрограмма hoare.bas

SUB HOARE(X% (),N%)

QUICK X%(),0,N%-1

END SUB

SUB QUICK(X%(),LEFT%,RIGHT%)

DIM I,J,XX,YY

I=LEFT%: J=RIGHT%

XX=X((LEFT%+RIGHT%)\2)

DO

WHILE X%(I) < XX AND I < RIGHT%: I=I+1: WEND

WHILE XX < X%(J) AND J > LEFT%: J=J-1: WEND

IF I <= J THEN

YY=X%(I): X%(I)=X%(J): X%(J)=YY: 1=1+1: J=J-1

END IF

LOOP WHILE I <= J

IF LEFT% < J THEN QUICK X%(),LEFT%,J

IF I < RIGHT% THEN QUICK X%(),I,RIGHT%

END SUB

Поиск

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

В достаточно общих чертах задача поиска формулируется следующим образом. Имеется массив а, содержащий п однородных объектов (чисел, строк, записей), и нужно установить, содержится ли в нем заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс) j найденного объекта (a[j] = q).

Последовательный поиск

Если исходный массив а не упорядочен, то единственно разумным способом является последовательный перебор всех элементов массива и сравнение их с заданным значением. В лучшем случае мы можем получить ответ на первом же шаге, если q = а [ 1 ]. В худшем случае придется перебрать все п элементов и только после этого дать положительный или отрицательный ответ. В среднем количество проверок может оказаться порядка п/2.
Классический алгоритм последовательного поиска включает следующие шаги:
S1 Остановить начальный индекс равным 1 (j = 1).
S2:Проверить условие q = a[j]. Если оно выполняется, то сообщить, что искомое значение находится в массиве а на j-ом месте и прервать работу. В противном случае продолжить работу.
S3:Увеличить индекс j на 1.
S4:Проверить условие j < n + 1. Если оно выполняется, то вернуться к шагу S2. В противном случае сообщить, что значение q в массиве а не содержится.
Большинству программистов кажется, что приведенный алгоритм является оптимальным и ничего сократить в нем нельзя. Однако это - очень распространенное заблуждение. Д. Кнут приводит модификацию алгоритма последовательного поиска, в которой цикл содержит не две логические проверки (шаги S2 и S4), а всего одну. В нашем случае это довольно существенно, т. к. описанный выше цикл реализуется пятью-шестью машинными командами и исключение из него даже одной команды эквивалентно повышению производительности на 15-20%.
Модификация состоит в том, что к массиву а добавляется еще один элемент, в который до начала цикла заносится q. Теперь цикл повторяется до тех пор, пока не будет встречен элемент а [ j ], равный q, и необходимость в проверке j < n + 1 отпадает. Конечно, перед возвратом из процедуры надо удостовериться в том, что найденный индекс j не равен n + l. Но такая проверка выполняется за пределами цикла.
Для программистов, имеющих дело с языком ассемблера, известен и более простой прием, не требующий расширения исходного массива. Очевидно, цикл поиска можно организовать как в прямом (j меняется от 1 до n), так и в обратном (j меняется от n до i) направлении. Обратный цикл на ассемблере реализуется с помощью команды LOOP, организующей возврат в начало цикла с одновременным вычитанием 1 из счетчика сх. Цикл повторяется до тех пор, пока содержимое регистра сх не станет равным 0. Таким образом, дополнительного сравнения (j < n + 1) здесь не требуется.
В приводимых ниже программах последовательного поиска возвращаемое соответствующей функцией значение либо равно индексу найденного элемента, либо равно - 1, если искомая величина в массиве не обнаружена.

Функция ssearch.bas

FUNCTION SSEARCH(Q,A(),N)

FOR J=0 TO N-l

IF Q=A(J) THEN SSEARCH=J: EXIT FUNCTION

NEXT J

SSEARCH=-1

END FUNCTION

Бинарный поиск

Бинарный поиск, суть которого была раскрыта выше на примере поимки льва в пустыне, применяется только для предварительно упорядоченных массивов. Несмотря на абсолютную прозрачность идеи деления пополам, ее программная реализация требует большой аккуратности как в использовании сравнений, так и в выборе очередного интервала поиска.
Исключим тривиальный случай, когда искомое значение g выходит за пределы интервала [а[1],а[n]]. Обозначим через left и right индексы элементов массива, определяющие текущий диапазон поиска. В начальный момент left = 1 и right = n. Сравним значение q с величиной среднего элемента a [mid] в диапазоне поиска (mid = (left + right)/2). Если значение q строго меньше a [mid], то заменим правую границу диапазона поиска на mid - 1. Если значение q строго больше a [mid], то заменим левую границу диапазона поиска на mid + 1. Если оба строгие неравенства не выполнены, то имеет место равенство q = a [mid], и в этом случае процедура поиска завершена успешно.
Поиск следует продолжать до тех пор, пока значение индекса left не превосходит значения индекса right. А нарушиться это условие может только в случае, когда диапазон поиска сведен к минимальному (right = left + l) и имеют место неравенства:
a[left] < q < a[right]
Это означает, что значение q в массиве а не содержится.
Функция bsearch.bas

FUNCTION BSEARCH(Q,A(),N) LEFT=0: RIGHT=N-1

WHILE LEFT <= RIGHT

MIDDLE=(LEFT+RIGHT)\2

IF Q < A(MIDDLE) THEN RIGHT=MIDDLE-1: GOTO M

IF Q > A(MIDDLE) THEN LEFT=MIDDLE+1: GOTO M

BSERACH=MIDDLE: EXIT FUNCTION M:WEND

BSEARCH=-1 END FUNCTION

Идея бинарного поиска может быть с успехом реализована в игре с отгадыванием задуманного целого числа из заранее установленного диапазона [O,N]. В ответ на число, предложенное угадывающим, его партнер может дать один из трех ответов:
это число меньше загаданного;
это число больше загаданного;
это число равно загаданному.
Оптимальное поведение отгадывающего в точности повторяет схему бинарного поиска. Сначала надо предложить число, расположенное в середине интервала, т. е. N/2. Затем, сузив интервал поиска вдвое, повторить аналогичный маневр. Попадание в цель произойдет не более чем через log₂N шагов.
Приведенные ниже тексты программ реализуют оптимальную тактику отгадывания чисел из диапазона [0,100], затрачивая на это не более 7 шагов. На вопросы программы загадавший должен нажимать клавишу Y или у (в случае положительного ответа) или любую другую клавишу, если вопрос программы не соответствует загаданному числу.

Программа 4_02.bas

'Программа угадывания задуманного числа в интервале [0,100]

DEFINT A-Z

CLS

LEFT=0: RIGHT=100:

DO

MIDDLE=(LEFT+RIGHT)\2

PRINT "Задуманное Вами число больше, чем"; MIDDLE; " (Y/N) - ";

INPUT "",A$

IF RIGHT-LEFT <= 1 THEN

IF A$="Y" OR A$="y" THEN

PRINT "Вы задумали ";RIGHT: END

ELSE

PRINT "Вы задумали ";LEFT: END

END IF

END IF

IF A$="Y" OR A$="y" THEN LEFT=MIDDLE+1 ELSE RIGHT=MIDDLE

LOOP

END