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

Сортировка выбором (англ. selection sort) — простой алгоритм сортировки со сложностью [math]O(n^2)[/math], где [math]n[/math] — количество элементов для сортировки.

Алгоритм

1. Находим номер минимального элемента из текущего массива.

2. Меняем минимальный элемент с первым элементом массива.

3. Если текущий массив пуст, то данный массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из текущего массива.

Реализация

 // Входной массив x, содержащий n элементов.
 for i = 0 to n - 1
    min = i;
       for j = i + 1 to n - 1
          if x[j] < x[min]
             min = j;
    swap(x[i], x[min]);
 // Массив x отсортирован

Пример

Пусть дана последовательность из [math]6[/math] элементов [math]5, 4, 1, 6, 2, 3[/math].

До	После	Описание шага
Первый проход (проталкиваем второй элемент — 2)
5 2 4 3 1	2 5 4 3 1	Алгоритм сравнивает второй элемент с первым и меняет их местами.
Второй проход (проталкиваем третий элемент — 4)
2 5 4 3 1	2 4 5 3 1	Сравнивает третий со вторым и меняет местами
2 4 5 3 1	2 4 5 3 1	Второй и первый отсортированы, swap не требуется
Третий проход (проталкиваем четвертый — 3)
2 4 5 3 1	2 4 3 5 1	Меняет четвертый и третий местами
2 4 3 5 1	2 3 4 5 1	Меняет третий и второй местами
2 3 4 5 1	2 3 4 5 1	Второй и первый отсортированы, swap не требуется
Четвертый проход (проталкиваем пятый элемент — 1)
2 3 4 5 1	2 3 4 1 5	Меняет пятый и четвертый местами
2 3 4 1 5	2 3 1 4 5	Меняет четвертый и третий местами
2 3 1 4 5	2 1 3 4 5	Меняет третий и второй местами
2 1 3 4 5	1 2 3 4 5	Меняет второй и первый местами. Массив отсортирован.

Ссылки

• Сортировка выбором в русской википедии

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4