Изменения

Перейти к: навигация, поиск

Сортировка выбором

2896 байт добавлено, 22:48, 20 мая 2012
Нет описания правки
== Алгоритм ==
[[file:Selection_sort.png|thumb|240px|Пример работы алгоритма для последовательности из 6 элементов]]
 
1. Находим номер минимального элемента из текущего массива.
3. Если текущий массив пуст, то данный массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из текущего массива.
 
 
'''Пример'''
 
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.
 
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.
== Реализация ==
swap(x[i], x[min]);
// Массив x отсортирован
 
== Пример ==
 
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.
 
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
!style="background-color:#EEE"| После
!style="background-color:#EEE"| Описание шага
|-
|colspan=3|''Первый проход (проталкиваем второй элемент — '''''2''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| '''5 2''' 4 3 1
|style="background-color:#FFF;padding:2px 10px"| '''2 5''' 4 3 1
|style="background-color:#FFF;padding:2px 10px"| Алгоритм сравнивает второй элемент с первым и меняет их местами.
|-
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''4''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''5 4''' 3 1
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 5''' 3 1
|style="background-color:#FFF;padding:2px 10px"| Сравнивает третий со вторым и меняет местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется
|-
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''5 3''' 1
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''3 5''' 1
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 3''' 5 1
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 4''' 5 1
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется
 
|-
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''1''''')''
|-
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''5 1'''
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''1 5'''
|style="background-color:#FFF;padding:2px 10px"| Меняет пятый и четвертый местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''4 1''' 5
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''1 4''' 5
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами
|-
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 1''' 4 5
|style="background-color:#FFF;padding:2px 10px"| 2 '''1 3''' 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами
|-
|style="background-color:#FFF;padding:2px 10px"| '''2 1''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| '''1 2''' 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.
|}
 
== Ссылки ==
93
правки

Навигация