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