- Сравниваются
- Текущий минимум
- Обменяны
- На месте
Сортировка выбором
Сортировка выбором строит отсортированный список с начала. Каждый проход просматривает ещё не отсортированные значения, запоминает наименьшее и обменом ставит его на первое неотсортированное место. Запускайте сортировку с любой скоростью или проходите её по одному сравнению и следите за счётчиками сравнений, обменов и проходов. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Плитки считают сравнения, обмены и проходы. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
- Следите, как по ходу просмотра меняется текущий минимум и как обмен в конце каждого прохода ставит его на место.
Как работает сортировка выбором
Просмотрите все значения в списке и запомните наименьшее. Поменяйте его местами с первым значением: первое место теперь окончательное. Затем сделайте то же самое с остальной частью списка, начиная на одно место дальше. После n − 1 проходов каждое значение стоит на своём месте, а последнее оказывается там само собой.
Много сравнений, мало обменов
Просмотр никогда не заканчивается раньше, потому что только после проверки каждого оставшегося значения можно быть уверенным, какое из них наименьшее. Поэтому сортировка выбором делает ровно n(n − 1)/2 сравнений для n значений, будь список отсортированным, обратным или случайным. Зато она делает не больше n − 1 обменов, по одному за проход. Поэтому она подходит, когда переместить значение гораздо дороже, чем сравнить два.
Часто задаваемые вопросы
Как работает сортировка выбором?
Она раз за разом выбирает наименьшее ещё не отсортированное значение и обменом ставит его на первое неотсортированное место. После k-го прохода на первых k местах стоят k наименьших значений по порядку.
Сколько сравнений и обменов делает сортировка выбором?
Всегда n(n − 1)/2 сравнений для n значений: 45 для 10 значений, 780 для 40. Обменов не больше n − 1, по одному за проход, и меньше, если наименьшее значение уже на месте.
Почему отсортированный список сортируется так же долго, как обратный?
Потому что каждый проход должен просмотреть все оставшиеся значения, чтобы убедиться, что нашёл наименьшее. В отличие от сортировки пузырьком и сортировки вставками, сортировка выбором не может понять по своим сравнениям, что список уже отсортирован.
Устойчива ли сортировка выбором?
В обычном виде нет. Обмен может перенести значение через равное ему: в 2, 2, 1 первая двойка меняется местами с единицей и оказывается за второй двойкой. Вариант, который сдвигает значения вместо обменов, устойчив, но ценой большего числа перемещений.
Мои числа куда-нибудь отправляются?
Нет. Сортировка выполняется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор