p align="justify"> В· кількість кроків алгоритму, необхідних для впорядкування;
В· кількість порівнянь елементів;
В· кількість перестановок, виконуваних при сортуванні. [1]
Найпростішим методом сортування є так званий метод В« бульбашки В». Щоб усвідомити його ідею, уявіть, що масив (таблиця) розташований вертикально. Елементи з великим значенням спливають нагору на зразок великих бульбашок. При першому проході уздовж масиву, починаючи прохід В«знизуВ», береться перший елемент і по черзі порівнюється з подальшими. При цьому:
В· якщо зустрічається більш В«легкийВ» (з меншим значенням) елемент, то вони міняються місцями;
В· при зустрічі з більш В«важкимВ» елементом, останній стає В«еталономВ» для порівняння, і все наступні порівнюються з ним.
В результаті найбільший елемент опиняється в самому верху масиву.
Під час другого проходу вздовж масиву знаходиться другий за величиною елемент, який міститься під елементом, знайденим при першому проході, тобто на другу зверху позицію, і т.д.
Зауважимо, що при другому і наступних проходах, немає необхідності розглядати раніше В«спливлиВ» елементи, тому що вони свідомо більше залишилися. Іншими словами, під час j -го проходу не перевіряються елементи, які стоять на позиціях вище j .
Алгоритм даної сортування вважається навчальним і практично не застосовується поза навчальної літератури, замість нього на практиці застосовуються більш ефективні алгоритми сортування. У той же час метод сортування обмінами лежить в основі деяких більш досконалих алгоритмів, таких як шейкерні сортування і пірамідальна сортування . [1]
шейкерні сортування (сортування перестановками) - різновид бульбашкового сортування. Аналізуючи метод бульбашкового сортування можна відзначити дві обставини.
По-перше, якщо при русі по частині масиву перестановки не відбуваються, то ця частина масиву вже відсортована і, отже, її можна виключити з розгляду. [1]
друге, при русі від кінця масиву до початку мінімальний елемент В«спливаєВ» на першу позицію, а максимальний елемент зсувається тільки на одну позицію вправо. [1]
Ці дві ідеї призводять до наступних модифікаціям в методі бульбашкового сортування. Межі робочої частини масиву (тобто частини масиву, де...
