Изменения

На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив , отсортированный по неубыванию.

Будем каждый раз проходить по всем еще не отсортированным элементам, и, как только найдем элемент меньше, чем первый из неотсортированных, поменяем их местами. Таким образом будет нужно <tex>O(n^2)</tex> обменов (для каждого <tex>i</tex> нужно требуется <tex>O(n-i)</tex> обменов). '''function''' SelectionSortselectionSort(array a):

swap(a[i], a[j]);

Второй вариант немного более экономный. Здесь мы будем менять местами элементы только <tex>1</tex> раз для каждого <tex>i</tex>, всего будет нужно <tex>O(n)</tex> обменов. Для этого сначала мы будем проходить по всем еще не отсортированным элементам, искать минимальный, и только потом менять местами минимальный и первый из неотсортированных.

'''function''' SelectionSortselectionSort(array a):

min = i;

min = j; swap(a[i], a[min]);

Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>. Будем выделять минимальный и текущий элемент на каждом шаге темно-зеленым цветом.

|style="background-color:#FFF;padding:2px 10px"| 5 4 <span style="color:darkgreen">'''1''' </span> 2 3|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} <span style="color:darkgreen">'''1''' </span>

|style="background-color:#FFF;padding:2px 10px"| <span style="color:darkgreen">'''1''' </span> 4 <span style="color:darkgreen">'''5''' </span> 2 3

|style="background-color:#FFF;padding:2px 10px"| 1 5 4 <span style="color:darkgreen">'''2''' </span> 3|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} <span style="color:darkgreen">'''2''' </span>

|style="background-color:#FFF;padding:2px 10px"| 1 <span style="color:darkgreen">'''2''' </span> 4 <span style="color:darkgreen">'''5''' </span> 3

|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 <span style="color:darkgreen">'''3'''</span>|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} <span style="color:darkgreen">'''3''' </span>

|style="background-color:#FFF;padding:2px 10px"| 1 2 <span style="color:darkgreen">'''3''' </span> 5 <span style="color:darkgreen">'''4'''</span>

|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 <span style="color:darkgreen">'''4'''</span>|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} <span style="color:darkgreen">'''4''' </span>

|style="background-color:#FFF;padding:2px 10px"| 1 2 3 <span style="color:darkgreen">'''4''' </span> <span style="color:darkgreen">'''5'''</span>

*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Википедия {{- --}} Сортировка выбором]