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

Матеріал з Вікіпедії — вільної енциклопедії.

Сортування вибором — простий алгоритм сортування лінійного масиву. Робота алгоритма складається з декількох етапів, на кожному етапі в ще невідсортованої частині масиву знаходиться мінімальний елемент і поміщається на початок цієї частини:

Search_Sort(A)
1 for i\gets\;1 to length[A] − 1
2     do j\gets\;Min\_Element(A,i)
3        Поміняти A[i]\leftrightarrow\;A[j]

Допоміжна процедура Min_Element здійснює пошук мінімального елементу в масиві починаючи з заданого індексу:

Min_Element(A,i)
1 x\gets\;i
2 for j\gets\;i+1 to length[A]
3     do if A[x] > A[j]
4           then x\gets\;j

[ред.] Аналіз роботи

В процесі своєї роботи алгоритм виконує O(n2) порівнянь і O(n) перестановок елементів масиву. Для роботи необхідно O(1) додаткової пам'яті.

Алгоритм є ефективним лише при невеликих розмірах масиву A. Також сортування вибором є стабільним.