Сортировка выбором¶
Сортировка выбором (selection sort) работает очень просто: запускается цикл, и на каждом шаге из неотсортированного диапазона выбирается минимальный элемент, после чего он переносится в конец уже отсортированного диапазона.
Пусть длина массива равна \(n\). Тогда процесс сортировки выбором выглядит так, как показано на рисунке ниже.
- В начальном состоянии все элементы не отсортированы, то есть неотсортированный диапазон индексов равен \([0, n-1]\) .
- Выбрать минимальный элемент из диапазона \([0, n-1]\) и поменять его местами с элементом в позиции \(0\) . После этого первый элемент массива отсортирован.
- Выбрать минимальный элемент из диапазона \([1, n-1]\) и поменять его местами с элементом в позиции \(1\) . После этого первые два элемента массива отсортированы.
- Продолжать по аналогии. После \(n - 1\) раундов выбора и обмена первые \(n - 1\) элементов массива будут отсортированы.
- Оставшийся элемент обязательно является максимальным, сортировать его не нужно, поэтому массив считается отсортированным.
В коде мы используем \(k\) для записи минимального элемента в пределах неотсортированного диапазона:
Характеристики алгоритма¶
- Временная сложность равна \(O(n^2)\), сортировка не является адаптивной: внешний цикл выполняется \(n - 1\) раз. В первом раунде длина неотсортированного диапазона равна \(n\) , а в последнем - \(2\) , то есть отдельные раунды содержат \(n\), \(n - 1\), \(\dots\), \(3\), \(2\) проходов внутреннего цикла, их сумма равна \(\frac{(n - 1)(n + 2)}{2}\) .
- Пространственная сложность равна \(O(1)\), сортировка выполняется на месте: указатели \(i\) и \(j\) используют константный объем дополнительной памяти.
- Нестабильная сортировка: как показано на рисунке ниже, элемент
nums[i]может быть переставлен вправо от другого равного ему элемента, из-за чего их относительный порядок изменится.
