2018-01-08
444
Лабораторна робота № 1
Лабораторна робота № 1
Тема роботи: Метод сортування бульбашкою.
Мета роботи: Вивчити алгоритм сортування бульбашкою. Здійснити програмну реалізацію алгоритму сортування бульбашкою. Дослідити швидкодію алгоритму сортування бульбашкою.
Короткі теоретичні відомості
Сортування бульбашкою (англійською «BubbleSort») — простий алгоритм сортування. Алгоритм працює наступним чином — у поданому наборі даних (списку чимасиві) порівнюються два сусідні елементи. Якщо один з елементів, не відповідає критерію сортування (є більшим, або ж, навпаки, меншим за свого сусіда), то ці два елементи міняються місцями. Прохід по списку продовжується до тих пір, доки дані не будуть відсортованими. Алгоритм отримав свою назву від того, що процес сортування згідно нього нагадує поведінку бульбашок повітря у резервуарі з водою. Оскільки для роботи з елементами масиву він використовує лише порівняння, це сортування на основі порівнянь.
Складність алгоритму у найгіршому у середньостатистичному випадку рівна О (n ²), де n — кількість елементів для сортування. Існує чимало значно ефективнішихалгоритмів, наприклад, з найгіршою ефективністю рівною O (n ∙log(n)). Тому даний алгоритм має низьку ефективність у випадках, коли N є досить великим, за винятком рідких конкретних випадків, коли заздалегідь відомо, що масив з самого початку буде добре відсотований.
Хоча, алгоритм є одним із найпростіших алгоритмів сортування, його ефективність є досить низькою, і він погано підходить для сортування великих списків. Більшість інших алгоритмів з такою ж швидкодією O (n 2) є ефективнішими за алгоритм сортуванням бульбашками, наприклад, сортування включенням.
Через свою простоту, алгоритм часто використовується для пояснення студентам концепції алгоритмів, та алгоритмів сортування, зокрема. Однак, деякі дослідники, як то Оуен Астрахан ретельно дослідивши даний алгоритм, стверджують, що він настільки поганий і неефективний, що вони навіть не використовуватимуть його в якості прикладу у своїй викладацькій діяльності.
Дональд Кнут у своїй знаменитій праці «TheArtofComputerProgramming» прийшов до висновнку, що «немає жодних підстав рекомендувати використовувати даний алгоритм, окрім, хібащо через примітну назву і через те, що він є лідером у кількості цікавих теоретичних пробем», частину з яких він обговорює у своїй праці.
Сортування бульбашкою під час своєї роботи є асимптоматичним еквівалентом алгоритму сортування включенням, у своєму найгіршому випадку, однак, обидваалгоритми дуже сильно відрізняються кількістю необхідних операцій переміщення. Результати низки експериментів, наприклад, проведених Астраханом також підверджують той факт, що продуктивність алгоритму сортування включенням є значно вищою. Тому багато сучасних посібників з алгоритмів навіть не згадують про алгоритм сортування бульбашками, і віддають перевагу сортуванню включеннями.
Сортування бульбашкою також погано використовує можливості сучасних мікропроцесорів. Він вимагає щонайменше удвічі більше операцій, ніж сортування включенням, удвічі більше кеш пам’яті, і асимптоматично більше передбачень переходів. Результати експериментів проведених Астраханом показали, що сортування рядка за алгоритмом сортування бульбашками у п’ять разів повільніше за сортування того ж рядка за алгоритмом сортування включенням і на 40% повільніше за сортування за алгоритмом сортування вибором.
