Предположим, что столбцы вверху — это люди; да, опять! Мы собираемся понять, как они будут стоять в отсортированном порядке. Все люди выше хотят простой способ стоять в порядке возрастания. Посмотрим, как пойдет.

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

Все вышеперечисленные люди решают сделать раздел, где люди стоят в отсортированном порядке. Они решили не использовать дополнительное пространство для этого раздела. Они знают, что самый низкий человек будет стоять на первой позиции в конце первого раунда. Выяснив, кто самый низкий, человек, стоящий на первой позиции, должен поменяться местами с самым низким. Я знаю, я знаю, это очень запутанно! Посмотрим, что будет в первом туре -

Они посмотрели друг на друга и увидели, что Б был самым низким. Поскольку это был первый раунд, самый короткий должен быть на первой позиции. Таким образом, B меняет местами с A. B теперь в белом, так как он находится в своей конечной отсортированной позиции. Теперь они не будут включать его в процесс сортировки. Далее A, C, D, E повторяют процесс.

Теперь B и D отсортированы. Хотя C, A, D тоже отсортированы, но их все равно нужно проверять. Они видят, что следующим кратчайшим является C, но он уже находится в правильном месте. То же самое с A и E. После окончания следующих раундов -

Ключевые моменты

  1. В конце каждого раунда первый элемент находится в отсортированном месте.
  2. Если говорить о времени, то оно занимает меньше времени, так как меняется только один раз в каждом раунде.
  3. Это не требует дополнительного места.

Сортировка выбора говорит,

«Поддерживайте два раздела — «Сортировка» и «Несортировка»! Найдите минимум в несортированном и поместите его в раздел «Сортировка».

Псевдокод :

Говоря о временной сложности - работают два цикла. Если посчитать общее количество сравнений, получится около N²/2. Вот почему временная сложность равна O(N²), так как она приблизительно равна времени, затрачиваемому в худшем случае. В лучшем случае то же самое, поскольку количество сравнений для поиска минимального элемента остается неизменным, даже если элемент находится в нужном месте.

Удачного кодирования!