СОРТИРОВКА методом бульбашки

Цей метод дуже простий він практично не вимагає робочих осередків, але працює досить повільно Однак його легко зрозуміти і він може служити ідеальним методом сортування загального призначення в умовах, коли память ЕОМ обмежена, а час виконання не дуже суттєво

Цей метод заснований на попарному порівнянні суміжних елементів даних якщо порядок проходження елементів в черговий парі неправильний, то ці елементи обмінюються місцями Для виконання обміну потрібна додаткова змінна, яка зберігає на час обміну одне зі значень Якщо значення, якими треба обмінятися, містяться в змінних А і В, то обмін можна виконати за допомогою операторів

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

що використовують змінну Т (в якості робочої комірки) Обмін значеннями строкових змінних здійснюється аналогічним чином

Обговоримо сортування числових значень в порядку убування Застосування методу бульбашки до масиву з розміром 4 ілюструє рис 42:

(А) Пройдіться по масиву від першого елемента до останнього, вибираючи по черзі пару суміжних значень Якщо ліве значення менше правого, то виконайте обмін значеннями Це гарантує переміщення найменшого значення в останній елемент масиву, хоча інші значення не зобовязані

Рис 42 Стадії бульбашкового сортування масиву з чотирьох значень

стати впорядкованими Тепер обмежтеся залишилися значеннями, що знаходяться в елементах від першого до передостаннього

(Б) Застосуйте процедуру (а) до Сократа безлічі значень, що знаходяться в елементах від першого до передостаннього Як і при першому проході, це гарантує переміщення найменшого значення в розглянутому безлічі в свою кінцеву позицію – в передостанній елемент масиву

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

Таким чином, при застосуванні цього методу кожен наступний прохід стає все коротшим і значення займають свої місця у напрямку від кінця масиву до його початку Кожен прохід забезпечує переміщення найменшого значення в кінець розглянутої порції масиву, тобто підйом вгору в правильну позицію

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

1000 REM ФРАГМЕНТ ПРОГРАМИ бульбашкового сортування

1010 REM припускали, що значення МІСТЯТЬСЯ

1020 REM У МАСИВІ А (1), … A

1030 REM У порядку убування

1040 FOR I=N TO 2 STEP -1

1050   FOR J=1 TO I-1

1060     IF A(J)&gt=A(J+1) THEN 1100

1070     T=A(J)

1080     A(J)=A(J+1)

1090     A(J+1)=T

1100   NEXT J

1110 NEXT I

1120 REM КІНЕЦЬ СОРТУВАННЯ

Для сортування даних у порядку зростання треба попросту змінити Умова в рядку 1060 на <=. Строкові дані можна сортувати в строковому масиві А $, використовуючи робочу строкову змінну Т $.

Іноді з кожним логічним елементом даних асоціюється кілька змінних, скажімо прізвище в А $ і адреса в В $ нехай, наприклад, ці масиви описані оператором

10 DIM А $ (95), В $ (95)

Сортування за прізвищами в AS здійснюється так, як описано вище, однак тепер в програму потрібно додати оператори, що забезпечують виконання в B $ в точності тих же переміщень, які відбуваються в AS Для цього рядка 1060 1090 треба замінити на оператори

1060             IF  A$(J)&gt=A$( J+1)   THEN   1100

1065           T$=A$(J)

1070          A$( J)=A$(J+l)

1075          A$(J+1)=T$

1085            T$=B$(J)

1085            B$(J)=B$(J+l)

1090            B$(J+1)=T$

Якщо при сортуванні треба враховувати тільки декілька перших літер прізвища, то в рядку 1060 можна виконувати витяг цих символів і порівняння Наприклад, якщо враховується три символи, то при роботі з Бейсиком Microsoft рядок 1060 треба замінити на оператор

1060  IF LEFT$(A$(J),3) &gt= LEFT$(A$(J + 1),3) THEN 1100

Щоб оцінити швидкість цього методу, визначимо число порівнянь значень На першому проході порівнюється (N-1) пара значень, на другому (N-2) пари на кожному наступному проході число порівнянь убуває на 1, поки не стане рівним 1 Таким чином, загальне число порівнянь

Якщо в певній частині випадків, скажімо в половині, за цими порівняннями послідує обмін значеннями, то число обмінів виявиться приблизно рівним N2 / 4 Тому повне час виконання сортування пропорційно N2, де N число сортируемих елементів даних

Джерело: Уолш Б Програмування на Бейсике: Пер з англ М: Радіо і звязок, 1988 336 с: ил

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*