ування. Хоча цей алгоритм сортування поступається в ефективності складнішим (таким як швидке сортування), у нього є ряд переваг:
. ефективний на невеликих наборах даних, на наборах даних до десятків елементів може виявитися кращим;
. ефективний на наборах даних, які вже частково відсортовані;
це стійкий алгоритм сортування (не змінює порядок елементів, які вже відсортовані);
. може сортувати список у міру його отримання;
використовує O (1) тимчасової пам'яті, включаючи стек.
Мінусом же є висока складність алгоритму
Опис:
На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку, до тих пір, поки набір вхідних даних не буде вичерпано. Метод вибору чергового елемента з вихідного масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються по порядку їх появи у вхідному масиві. Наведений нижче алгоритм використовує саме цю стратегію вибору. p align="justify"> Аналіз алгоритму
Час виконання алгоритму залежить від вхідних даних: чим більша безліч потрібно відсортувати, тим більший час виконується сортування. Також на час виконання впливає вихідна впорядкованість масиву. Так, кращим випадком є ​​відсортований масив, а гіршим - масив, відсортований в порядку, зворотному потрібного. Тимчасова складність алгоритму при гіршому варіанті вхідних даних
Сортування вибором
Алгоритм може бути реалізований і як стійкий і як нестійкий. На масиві з n елементів має час виконання в гіршому, середньому і кращому випадку ? (n2), припускаючи що порівняння робляться за постійний час.
Алгоритм
Кроки алгоритму:
. знаходимо мінімальне значення в поточному списку
. проводимо обмін цього значення зі значенням на першій невідсортованої позиції
. тепер сортуємо хвіст списку, виключивши з розгляду вже відсортовані елементи
Аналіз сортування
На жаль як і в сортуванні бульбашковим методом зовнішній цикл виконується n-1 раз, а внутрішній цикл виконується n/2 разів. Це означає, що число порівнянь для сортування вибором одно 1/2 (n2-n) і ця сортування буде виконуватися занадто повільно для великого числа елементів. Число операцій обміну в найкращому разі дорівнює 3 (n-1), а в гіршому випадку дорівнює n2/4 +3 (n-1). У кращому випадку (коли вихідний
масив вже впорядкований) буде потрібно поміняти місцями тільки n-1елементов, а кожна операція обміну вимагає т...
