Веселкова візуалізація алгоритмів сортування


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Якщо у вас є обмеження по сприйняттю кольору, то доступна версія для дальтоніків.

В усій візуалізації кожен ряд або стовпець пікселів є окремим незалежним масивом, який сортується одночасно з іншими.

Сортування бульбашкою

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

Опис алгоритму на Вікіпедії

Вона ж, але збільшена і уповільнена версія, щоб було простіше зрозуміти суть:

Сортування перемішуванням

Її також називають шейкерною або коктейльною, свого роду різновид бульбашкової. І з візуалізації відразу зрозуміло, чому.

Опис алгоритму на Вікіпедії

Сортування вставками

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

Опис алгоритму на Вікіпедії

Сортування Шелла

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

Опис алгоритму на Вікіпедії

Сортування гребінцем

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

Опис алгоритму на Вікіпедії

Сортування злиттям

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

Опис алгоритму на Вікіпедії

Пірамідальне сортування

Цей алгоритм може розглядатися як вдосконалене сортування бульбашкою, в якому елемент спливає (min – heap) або тоне (max – heap) по багатьох шляхах, залежно від того, який тип двійкової купи застосовується. У візуалізації можна наочно порівняти швидкість в одному і іншому випадку. Можете повправлятися і спробувати пояснити, чому один з варіантів швидше.

Опис алгоритму на Вікіпедії

Швидке сортування

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

Опис алгоритму на Вікіпедії

І той же алгоритм, але не на випадкових даних, а на масиві, відсортованому в зворотному порядку :

Порозрядне сортування

Цей алгоритм сортує числа за лінійний час по розрядах. Існує два варіанти: most significant digit (MSD, на візуалізації ліворуч) і least significant digit (LSD, справа). При MSD сортуванні спочатку сортуються старші розряди, потім молодші, а при LSD все навпаки.

Опис алгоритму на Вікіпедії

Бітонне сортування

Цей алгоритм призначений для паралельного сортування даних на різних обчислювальних вузлах. У основі лежить поняття “Бітонної послідовності”, звідси і назва. Якщо дані дозволяють розбиття для паралельної обробки, цей спосіб може спрацювати набагато швидше за інших.

Опис алгоритму на Вікіпедії

Вона ж, трохи ближче і повільніше :

Порівняння алгоритмів за швидкістю

Зробивши стільки візуалізації, було б дивно не змусити їх змагатися між собою.

На випадковому наборі даних, як і очікувалося, коктейльне сортування (ліворуч) помітно програє. Друге ліворуч – сортування вставками, далі Шелла, і найправіше – сортування гребінцем:

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

Тепер порівняємо алгоритми, працюючі за O (n log n). Швидке сортування ліворуч, потім пірамідальне, злиттям, і найправіша – порозрядне.

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

Детальніше про алгоритми сортування для початківців ви можете прочитати в нашій статті з циклу “Алгоритми і структури даних”.

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

Джерело: Imgur

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Коментарі 1

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

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *