Сортування вставками
Будує зліва відсортовану частину, додаючи по одному значенню. Кожне нове значення виймається і рухається ліворуч, доки не натрапить на менше.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- так
- так
Найкраща: як росте час із розміром списку n, коли вхідні дані для цього алгоритму найлегші.
Середня: як зазвичай росте час із n. За n² удвічі більше значень - це приблизно вчетверо довше; n log n росте значно повільніше.
Найгірша: як росте час на найважчих вхідних даних. Важлива, коли швидкість ніколи не має падати.
Пам'ять: скільки додаткової пам'яті потрібно, крім списку. 1 - кілька змінних, n - копія списку.
Стабільне: два рівні значення зберігають свій початковий порядок. Важливо, коли сортуємо записи за одним полем.
Без додаткової пам'яті: сортує всередині самого списку, без другого списку.
- порівняння
- переміщення
- у руці
- відсортована частина
- на остаточному місці
Спробуйте: Оберіть майже відсортований список. Майже нічого не зсувається, тож сортування займає зовсім мало кроків.
Як це працює
Ліва частина завжди відсортована. Виймаємо наступне значення, зсуваємо кожне більше значення відсортованої частини на одну позицію праворуч і ставимо вийняте значення в порожнє місце. Так багато хто розкладає карти в руці.
Коли варто використовувати
Добрий вибір для коротких списків і для майже відсортованих, на яких воно дуже швидке. Бібліотеки сортування на практиці використовують його для дрібних частин списку всередині швидших методів.