Методи сортування в програмуванні: сортування "бульбашкою"
Сортування бульбашкою не тільки не вважається найшвидшим методом, більш того, вона замикає перелік найповільніших способів упорядкування. Проте і у неї є свої плюси. Так, сортування методом бульбашки – саме що ні на є логічне і природне рішення проблеми, якщо необхідно розставити елементи в певному порядку. Звичайна людина вручну, наприклад, скористається саме їм – просто по інтуїції.
Зміст
Звідки взялося таке незвичайне назва?
Назва методу придумали, використовуючи аналогію з повітряними бульбашками у воді. Це метафора. Подібно до того, як маленькі бульбашки повітря піднімаються нагору – адже їх щільність більше, ніж який-небудь рідини (в даному випадку – води), так і кожен елемент масиву, чим менше він за значенням, тим більше він поступово пробирається до початку переліку чисел.
Опис алгоритму
Сортування бульбашкою виконується таким чином:
- перший прохід: елементи масиву чисел беруться по два і також парами порівнюються. Якщо в якійсь двійці елементів перше значення виявляється більше другого, програма робить їх обмін місцями;
- отже, найбільше число потрапляє в кінець масиву. У той час як всі інші елементи залишаються, як і були, в хаотичному порядку і вимагають ще сортування;
- тому й потрібен другий прохід: проводиться він за аналогією з попереднім (вже описаним) і має число порівнянь – мінус один;
- біля проходу номер три порівнянь на одиницю менше, ніж у другого, і на двійку, ніж у першого. І так далі;
- підсумуємо, що кожен прохід має (всього значень в масиві, конкретне число) мінус (номер проходу) порівнянь.
сортування методом бульбашки
Ще коротше алгоритм майбутньої програми можна записати так:
- масив чисел перевіряється до тих пір, поки не будуть знайдені якісь два числа, причому друге з них має бути більше першого;
- неправильно розташовані по відношенню один до одного елементи масиву програма міняє місцями.
Псевдокод на основі описаного алгоритму
Найпростіша реалізація виконується так:
Процедура Sortirovka_Puzirkom-
початок
цикл для j від nachalnii_index до konechii_index-
цикл для i від nachalnii_index до konechii_index-1-
якщо massiv [i]> massiv [i + 1] (перший елемент більше другого), то:
(міняємо значення місцями) -
Кінець
Звичайно, тут простота тільки погіршує ситуацію: чим простіше алгоритм, тим більше в ньому проявляються всі вади. Витратність часу занадто велика навіть для невеликого масиву (тут вступає у справу відносність: для обивателя кількість часу може здаватися маленьким, але у справі програміста кожна секунда або навіть мілісекунда на рахунку).
Знадобилася реалізація получше. Наприклад, що враховує обмін значень у масиві місцями:
Процедура Sortirovka_Puzirkom-
початок
sortirovka = Істина-
цикл поки sortirovka = Істина-
sortirovka = Ложь-
цикл для i від nachalnii_index до konechii_index-1-
якщо massiv [i]> massiv [i + 1] (перший елемент більше другого), то:
(міняємо елементи місцями) -
sortirovka = Істина- (позначили, що обмін був проведений).
Кінець.
Недоліки методу
Основний мінус – тривалість процесу. Скільки ж часу виконується алгоритм сортування бульбашкою?
Час виконання розраховується з квадрата кількості чисел в масиві – кінцевий результат йому пропорційний.
При найгіршому варіанті масив буде пройдений стільки ж разів, скільки в ньому є елементів мінус одне значення. Так відбувається тому, що в кінцевому підсумку залишається тільки один елемент, який ні з чим порівнювати, і останній прохід по масиву стає марним дійством.
Крім того, ефективний метод сортування простими обмінами, як його ще називають, тільки для масивів невеликого розміру. Великі обсяги даних з його допомогою обробити не вийде: результатом стануть або помилки, або збій роботи програми.
паскаль сортування бульбашкою
Гідності
Сортування бульбашкою вельми проста для розуміння. У навчальних програмах технічних ВНЗ при вивченні упорядкування елементів масиву її проходять в першу чергу. Метод легко реалізується як на мові програмування Delphi (Д (Делфі), так і на C / C ++ (Сі / Сі плюс плюс), неймовірно простий алгоритм розташування значень у вірному порядку і на Pascal (Паскаль). Сортування бульбашкою ідеально підходить для початківців.
Унаслідок недоліків алгоритм не застосовують під позанавчальних цілях.
Наочний принцип сортування
Початковий вигляд масиву 8 22 4 74 44 37 1 7
Крок 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Крок 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Крок 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Крок 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Крок 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Крок 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Крок 7 1 4 7 8 22 37 44 74
Приклад сортування бульбашкою на мові Pascal
алгоритм сортування бульбашкою
Приклад:
const kol_mas = 10-
var massiv: array [1..kol_mas] of integer-
a, b, k: integer-
begin
writeln ('input', kol_mas, 'elements of array') -
for a: = 1 to kol_mas do readln (massiv [a]) -
for a: = 1 to kol_mas-1 do begin
for b: = a + 1 to kol_mas do begin
if massiv [a]> massiv [b] then begin
k: = massiv [a] - massiv [a]: = massiv [b] - massiv [b]: = k-
end-
end-
end-
writeln ('after sort') -
for a: = 1 to kol_mas do writeln (massiv [a]) -
end.
Приклад сортування бульбашкою на мові С (Сі)
Приклад:
#include
#include
int main (int argc, char * argv [])
{
int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff-
for (- -) {
ff = 0-
for (i = 7- i> 0- i -) {
if (massiv [i] lt; massiv [i-1]) {
swap (massiv [i], massiv [i-1]) -
ff ++ -
}
}
if (ff == 0) break-
}
getch () - // затримка екрану
return 0-
}.