Методи сортування в програмуванні: сортування "бульбашкою"

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

Звідки взялося таке незвичайне назва?

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

опис алгоритму

Сортування бульбашкою виконується наступним чином:

перший прохід: елементи масиву чисел беруться за два і також парами порівнюються. Якщо в якийсь двійці елементів перше значення виявляється більше другого, програма робить їх обмін місцями;
отже, найбільше число потрапляє в кінець масиву. У той час як всі інші елементи залишаються, як і були, в хаотичному порядку і вимагають ще сортування;
тому й потрібен другий прохід: проводиться він за аналогією з попереднім (вже описаним) і має число порівнянь - мінус один;
біля проходу номер три порівнянь на одиницю менше, ніж у другого, і на двійку, ніж у першого. І так далі;
підсумуємо, що кожен прохід має (всього значень в масиві, конкретне число) мінус (номер проходу) порівнянь.

Ще коротше алгоритм майбутньої програми можна записати так:

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

Псевдокод на основі описаного алгоритму

Найпростіша реалізація виконується так:

процедура Sortirovka_Puzirkom-

початок

цикл для j від nachalnii_index до konechii_index-

цикл для i від nachalnii_index до konechii_index-1-

якщо massiv [i] gt; massiv [i + 1] (Перший елемент більше другого), то:

(Міняємо значення місцями) -

кінець

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

Потрібна була реалізація краще. Наприклад, враховує обмін значень в масиві місцями:

процедура Sortirovka_Puzirkom-

початок

sortirovka = істина-

цикл поки sortirovka = істина-

sortirovka = ложь-

цикл для i від nachalnii_index до konechii_index-1-

якщо massiv [i] gt; massiv [i + 1] (Перший елемент більше другого), то:

(Міняємо елементи місцями) -

sortirovka = Істина- (позначили, що обмін був проведений).

Кінець.

недоліки методу

Основний мінус - тривалість процесу. Скільки ж часу виконується алгоритм сортування бульбашкою?

Відео: Паскаль з нуля [Ч12]. Сортування масиву методом бульбашки

Час виконання розраховується з квадрата кількості чисел в масиві - кінцевий результат йому пропорційний.

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

Крім того, ефективний метод сортування простими обмінами, як його ще називають, тільки для масивів невеликого розміру. Великі обсяги даних з його допомогою обробити не вийде: результатом стануть або помилки, або збій роботи програми.

переваги

Сортування бульбашкою вельми проста для розуміння. У навчальних програмах технічних ВНЗ при вивченні упорядкування елементів масиву її проходять в першу чергу. Метод легко реалізується як на мові програмування Delphi (Д (Делфі), так і на C / C ++ (Сі / Сі плюс плюс), неймовірно простий алгоритм розташування значень у вірному порядку і на Pascal (Паскаль). Сортування бульбашкою ідеально підходить для початківців.

Унаслідок недоліків алгоритм не застосовують під позанавчальних цілях.