Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.
Якщо у вас є обмеження по сприйняттю кольору, то доступна версія для дальтоніків.
В усій візуалізації кожен ряд або стовпець пікселів є окремим незалежним масивом, який сортується одночасно з іншими.
Сортування бульбашкою
Алгоритм вважається учбовим і практично не застосовується поза учбової літератури. На кожному проході порівнюються два сусідні елементи, і якщо їх порядок неправильний, вони міняються місцями. У результаті елемент як би спливає на своє місце.
Вона ж, але збільшена і уповільнена версія, щоб було простіше зрозуміти суть:
Сортування перемішуванням
Її також називають шейкерною або коктейльною, свого роду різновид бульбашкової. І з візуалізації відразу зрозуміло, чому.
Сортування вставками
У цьому сортуванні усі елементи масиву видимі по одному, і кожен поміщається в потрібне місце у вже відсортованій частині. Потішно, що вставки куди більше схожі на спливаючі бульбашки, чим у бульбашковому сортуванні.
Сортування Шелла
Ідея методу Шелла полягає в порівнянні елементів, що стоять не лише поряд, але і на певній відстані один від одного. Іншими словами, це сортування вставками з попередніми ” грубими” проходами.
Сортування гребінцем
Це сортування по суті є поліпшеним бульбашковим алгоритмом. Основна ідея в тому, що проміжок між порівнюваними елементами може бути більший, ніж одиниця, що дозволяє значно поліпшити ефективність.
Сортування злиттям
Цей алгоритм розбиває усю область сортування на частини і сортує їх рекурсивно, а потім зливає. На візуалізації ліва частина використовує рекурсію, що йде в глибину, а в правій – завширшки. Обидва способи обходу займають у результаті однаковий час.
Пірамідальне сортування
Цей алгоритм може розглядатися як вдосконалене сортування бульбашкою, в якому елемент спливає (min – heap) або тоне (max – heap) по багатьох шляхах, залежно від того, який тип двійкової купи застосовується. У візуалізації можна наочно порівняти швидкість в одному і іншому випадку. Можете повправлятися і спробувати пояснити, чому один з варіантів швидше.
Швидке сортування
Воно ж сортування Хоара – один з найпопулярніших алгоритмів із-за своєї універсальності і середньої швидкості. Принципова відмінність від сортувань прямими обмінами (наприклад, тим ж бульбашковим) полягає в тому, що в першу чергу робляться перестановки на найбільшій можливій відстані, і після кожного проходу елементи діляться на дві незалежні групи. Цікавий факт: поліпшення самого неефективного прямого методу сортування дало в результаті один з найбільш ефективних методів.
І той же алгоритм, але не на випадкових даних, а на масиві, відсортованому в зворотному порядку :
Порозрядне сортування
Цей алгоритм сортує числа за лінійний час по розрядах. Існує два варіанти: most significant digit (MSD, на візуалізації ліворуч) і least significant digit (LSD, справа). При MSD сортуванні спочатку сортуються старші розряди, потім молодші, а при LSD все навпаки.
Бітонне сортування
Цей алгоритм призначений для паралельного сортування даних на різних обчислювальних вузлах. У основі лежить поняття “Бітонної послідовності”, звідси і назва. Якщо дані дозволяють розбиття для паралельної обробки, цей спосіб може спрацювати набагато швидше за інших.
Вона ж, трохи ближче і повільніше :
Порівняння алгоритмів за швидкістю
Зробивши стільки візуалізації, було б дивно не змусити їх змагатися між собою.
На випадковому наборі даних, як і очікувалося, коктейльне сортування (ліворуч) помітно програє. Друге ліворуч – сортування вставками, далі Шелла, і найправіше – сортування гребінцем:
Ті ж алгоритми, але на відсортованому в зворотному порядку масиві. Помітно, що метод вставок спрацював ще повільніше:
Тепер порівняємо алгоритми, працюючі за O (n log n). Швидке сортування ліворуч, потім пірамідальне, злиттям, і найправіша – порозрядне.
Ті ж алгоритми ще раз, але цього разу в масиві тільки 8 унікальних значень. Цього разу швидке сортування впоралося гірше.
Детальніше про алгоритми сортування для початківців ви можете прочитати в нашій статті з циклу “Алгоритми і структури даних”.
Також подивіться інші візуалізації алгоритмів сортування, більше орієнтовані на учбові цілі.
Джерело: Imgur
Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?
Це дуже корисне нововведення у візуалізації алгоритмів сортування. Мій хороший знайомий володіє такою особливою рисою, він обмежений у сприйнятті кольорів. Так ось ця додаткова версія для дальтоніків тепер дозволить йому в повному обсязі сприймати побачене. Мені сподобалася інформація в статті про алгоритми сортування елементів. Пізнавально!
Дуже круто. Дякую