Предположим, что столбцы вверху — это люди; да, опять! Мы собираемся понять, как они будут стоять в отсортированном порядке. Все люди выше хотят простой способ стоять в порядке возрастания. Посмотрим, как пойдет.
Сортировка выбором
Все вышеперечисленные люди решают сделать раздел, где люди стоят в отсортированном порядке. Они решили не использовать дополнительное пространство для этого раздела. Они знают, что самый низкий человек будет стоять на первой позиции в конце первого раунда. Выяснив, кто самый низкий, человек, стоящий на первой позиции, должен поменяться местами с самым низким. Я знаю, я знаю, это очень запутанно! Посмотрим, что будет в первом туре -
Они посмотрели друг на друга и увидели, что Б был самым низким. Поскольку это был первый раунд, самый короткий должен быть на первой позиции. Таким образом, B меняет местами с A. B теперь в белом, так как он находится в своей конечной отсортированной позиции. Теперь они не будут включать его в процесс сортировки. Далее A, C, D, E повторяют процесс.
Теперь B и D отсортированы. Хотя C, A, D тоже отсортированы, но их все равно нужно проверять. Они видят, что следующим кратчайшим является C, но он уже находится в правильном месте. То же самое с A и E. После окончания следующих раундов -
Ключевые моменты
- В конце каждого раунда первый элемент находится в отсортированном месте.
- Если говорить о времени, то оно занимает меньше времени, так как меняется только один раз в каждом раунде.
- Это не требует дополнительного места.
Сортировка выбора говорит,
«Поддерживайте два раздела — «Сортировка» и «Несортировка»! Найдите минимум в несортированном и поместите его в раздел «Сортировка».
Псевдокод :
Говоря о временной сложности - работают два цикла. Если посчитать общее количество сравнений, получится около N²/2. Вот почему временная сложность равна O(N²), так как она приблизительно равна времени, затрачиваемому в худшем случае. В лучшем случае то же самое, поскольку количество сравнений для поиска минимального элемента остается неизменным, даже если элемент находится в нужном месте.
Удачного кодирования!