Полный анализ алгоритма сортировки выбором.
Эта статья посвящена разработке, визуализации и анализу алгоритма сортировки выбором. Прочитав эту статью, вы сможете ответить на большинство вопросов, связанных с алгоритмом сортировки выбором.
Что такое алгоритм сортировки выбором?
Алгоритм сортировки выбором сортирует элементы массива, находя минимальный элемент из несортированного подмассива и помещая элемент в отсортированный подмассив (учитывая сортировку элементов массива по возрастанию).
Алгоритм поддерживает два подмассива в заданном массиве.
- Отсортированный подмассив, содержащий отсортированные элементы.
- Остальные элементы, которые являются несортированными, остаются в несортированном подмассиве.
На каждой итерации алгоритма сортировки выбором минимальный элемент из несортированного подмассива выбирается и помещается в конец отсортированного подмассива (с учетом сортировки элементов массива по возрастанию).
Давайте визуализируем алгоритм сортировки выбором на примере:
Теперь давайте возьмем элементы массива как 9,7,5,3,1 и воспользуемся визуализацией сортировки выбором для сортировки этих элементов.
Итерация-1:
Итерация-2:
Итерация-3:
Итерация-4:
Окончательный подмассив (который равен исходному массиву):
Теперь давайте разработаем алгоритм сортировки выбором:
Для проектирования кода требуются два цикла.
- для перебора элементов массива.
- чтобы найти minIndex в массиве
Ниже фрагмент кода иллюстрирует это:
Анализ временной и пространственной сложности:
Как наилучшая, так и наихудшая временная сложность алгоритма сортировки выбором составляет O (n2), поскольку в обоих случаях выполняются внешний и внутренний циклы for. Приведенное ниже уравнение справедливо как для наилучшего, так и для наихудшего сценария:
Сколько раз внутренний цикл for’выполняется для n количества элементов:
(n-1) + (n-2) + (n-3) +… + 3 + 2 + 1 = n(n-1)/2
Следовательно, сортировка выбором имеет лучшую и худшую временную сложность O(n2).
Стабильна ли сортировка выбором?
Определение стабильного: сохраняется относительный порядок элементов с одинаковым значением.
Сортировка выбором не является стабильным алгоритмом.
По сути, в selection sort замена, которая происходит в конце каждой итерации, может изменить относительный порядок элементов, имеющих одинаковое значение.
Например, предположим, что у вас есть элементы массива как 4 2 3 4 1 с selection sort.
Первая итерация будет проходить через каждый элемент в поисках минимального элемента. Он обнаружит, что 1 является минимальным элементом. А затем он поменяет 1 на первое место, которое равно 4. Это приведет к тому, что 4 на первом месте переместятся на последнее место: 1 2 3 4 4
Теперь относительный порядок четверок изменился. Элемент «первый» 4 в исходном списке был перемещен на место после остальных 4.
Поэтому алгоритм сортировки выбором нестабилен.
Сортировка выбором на месте?
Он не использует дополнительное пространство для сортировки элементов массива, следовательно, это алгоритм сортировки на месте.
Это все для этой статьи. Спасибо, что прочитали эту статью. Надеюсь, вы поняли алгоритм сортировки выбором и его временные и пространственные сложности. Вы можете прочитать другие мои полезные статьи о сортировке структуры данных.
Ссылка: Введение в алгоритмы.
