Сортування вставками
Сортування вставками — інтерактивний експеримент із застосунку «Алгоритми в дії», безкоштовної симуляції StudyFi Lab, яка працює просто в браузері.
Сортування вставками схоже на впорядкування карт у руці: ліва частина вже впорядкована, а кожен наступний елемент (key) зсувається ліворуч, доки не зустріне менший. Більші елементи при цьому зсуваються на одне місце праворуч. На випадкових даних це O(n²), а на майже впорядкованих — майже O(n): упорядкованому масиву потрібно лише n−1 порівнянь.
Спробуй: Запусти його на майже впорядкованому масиві, а потім на зворотному. У скільки разів більше зсувів потрібно зворотному?
Поширені запитання
Що показує експеримент «Сортування вставками»?
Сортування вставками схоже на впорядкування карт у руці: ліва частина вже впорядкована, а кожен наступний елемент (key) зсувається ліворуч, доки не зустріне менший. Більші елементи при цьому зсуваються на одне місце праворуч. На випадкових даних це O(n²), а на майже впорядкованих — майже O(n): упорядкованому масиву потрібно лише n−1 порівнянь.
Як спробувати «Сортування вставками»?
Запусти його на майже впорядкованому масиві, а потім на зворотному. У скільки разів більше зсувів потрібно зворотному?
Готуєшся до контрольної?
Завантаж свої конспекти, і StudyFi перетворить їх на картки, тести й подкасти.