Сортування вибором простий алгоритм сортування лінійного масиву на основі вставок Має ефективність n2 що робить його нее

Сортування вибором — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n², що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю.

Сортування вибором

Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	О(n²)
Найкраща швидкодія	О(n²)
Середня швидкодія	О(n²)
Просторова складність у найгіршому випадку	О(n), O(1)
Оптимальний	Не практичний

Метод

Алгоритм працює таким чином:

Знаходить у списку найменше значення
Міняє його місцями із першим значенням у списку
Повторює два попередніх кроки, доки список не завершиться (починаючи з наступної позиції)

Фактично, таким чином ми поділили список на дві частини: перша (ліва) — повністю відсортована, а друга (права) — ні.

Ось приклад сортування масиву з п'яти елементів за даним алгоритмом:

64 25 12 22 11 11 25 12 22 64 11 12 25 22 64 11 12 22 25 64

Сортування вставками також може працювати зі списками, які підтримують операції додавання і видалення, як то зв'язаний список. У такому разі, більш зручно видаляти зі списку найменший елемент, і вставляти його в кінець відсортованої частини масиву. Наприклад:

64 25 12 22 11 11 64 25 12 22 11 12 64 25 22 11 12 22 64 25 11 12 22 25 64

Аналіз

Сортування вибором не є складним в аналізі та порівнянні його з іншими алгоритмами, оскільки жоден з циклів не залежить від даних у списку. Знаходження найменшого елементу вимагає перегляду усіх n елементів (у цьому випадку n − 1 порівняння), і після цього, перестановки його до першої позиції. Знаходження наступного найменшого елементу вимагає перегляду n − 1 елементів, і так далі, для (n − 1) + (n − 2) + … + 2 + 1 = n(n − 1) / 2 ∈ Θ(n²) порівнянь (дивіться арифметична прогресія). Кожне сканування вимагає перестановки однієї пари елементів, тож всього потрібно (n − 1) перестановок (останній елемент знаходитиметься на своєму місці).

Джерела

Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)

Посилання

Animated Sorting Algorithms: Selection Sort — графічна демонстрація роботи алгоритму.
Наочна демонстрація сортування вибором ромалами в танку.
Selection Sort Demo
Selection Sort Demo^{[недоступне посилання з липня 2019]}
Pointers to
C++ Program — Selection Sort
Selection sort explained and C++ source code

Це незавершена стаття про алгоритми.
Ви можете проєкту, виправивши або дописавши її.