Що таке представлення сортування вставкою?
Сортування вставкою є ан
алгоритм сортування на основі порівняння, який зазвичай використовується в інформатиці. Цей алгоритм схожий на те, як ми сортуємо колоду карт під час гри в бридж. Основна ідея списку вставок полягає в тому, що він вставляє кожен елемент у належне місце в остаточному відсортованому масиві. 30 грудня 2020 р.
Робота сортування вставкою з прикладом Один елемент завжди сортується. Отже, ми встановлюємо ключ рівним 5, а потім ми побачимо, де ми можемо розмістити цей ключ у відсортованому масиві. Як ми бачимо, 5 менше, ніж 6, тому ми переміщуємо 6 на одну позицію вперед і розміщуємо 5 перед 6. Тепер наш відсортований масив перетвориться на 5 6.
Сортування вставкою базується на ідеї, що один елемент із вхідних елементів споживається в кожній ітерації, щоб знайти його правильну позицію тобто позиція, до якої він належить у відсортованому масиві.
Він викликається на сегментах масиву довжиною від 1 до N, так що усереднює масиви довжиною N/2. Часова складність сортування вставленням становить O(N2), оскільки він використовує цикл for із N ітерацій, який викликає метод O(N).
Нотації великого O: Сортування вставкою: Також має a найкраща часова складність O(n) для вже відсортованого масиву, але має середню та найгіршу часову складність O(n²) за рахунок вкладених циклів для вставки елементів.
Часто використовується сортування вставкою упорядковувати невеликі списки. З іншого боку, сортування вставленням не є найефективнішим методом обробки великих списків із великою кількістю елементів. Примітно, що алгоритм сортування вставкою є кращим під час роботи зі зв’язаним списком.