Главная » Basic » СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА

0

Этот метод очень прост; он практически не требует рабочих ячеек, но работает довольно медленно. Однако его легко понять и он может служить идеальным методом сортировки общего назначения в условиях, когда память ЭВМ ограничена, а время исполнения не очень существенно.

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

10 Т=А 20 А = В 30   В=Т

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

Обсудим сортировку числовых значений в   порядке  убывания. Применение  метода  пузырька  к массиву с размером 4 иллюстрирует рис. 4.2:

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

Рис. 4.2. Стадии пузырьковой сортировки массива из четырех значений

стать упорядоченными. Теперь ограничьтесь  оставшимися значениями, находящимися в  элементах от первого до предпоследнего.

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

(в)  Рассмотрите оставшиеся значения и продолжайте действовать аналогичным образом.

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

Ниже приводится структограмма, изображающая метод пузырька, а также фрагмент программы:

Если в  определенной части случаев, скажем в половине,   за этими сравнениями  последует обмен значениями, то  число обменов окажется  приблизительно  равным N2/4.  Поэтому  полное  время выполнения сортировки пропорционально N2, где N число сортируемых элементов данных.

Источник: Уолш Б.    Программирование на Бейсике: Пер. с англ. М.: Радио и связь, 1988. 336 с: ил.

По теме:

  • Комментарии