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

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

Алгоритм

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

Реализация

Вариант 1.

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

Вариант 2.

 for i = 0 to n - 2
   for j = i + 1 to n - 1
     if a[i] > a[j]
       swap(a[i], a[j]);

Пример

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

Массив	Описание шага
Первый проход (текущий массив начинается с первого элемента)
5 4 1 2 3	Находим первый минимальный элемент — 1
1 4 5 2 3	Меняем минимальный и первый элементы местами
Второй проход (текущий массив начинается со следующего элемента)
1 5 4 2 3	Находим следующий минимальный элемент — 2
1 2 4 5 3	Меняем минимальный и второй элементы местами
Третий проход (текущий массив начинается со следующего элемента)
1 2 4 5 3	Находим следующий минимальный элемент — 3
1 2 3 5 4	Меняем минимальный и третий элементы местами
Четвертый проход (текущий массив начинается со следующего элемента)
1 2 3 5 4	Находим следующий минимальный элемент — 4
1 2 3 4 5	Меняем минимальный и четвертый элементы местами
1 2 3 4 5	Массив отсортирован

Ссылки

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

Литература

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