Сортировка - это базовая операция, в которой элементы массива располагаются в определенном порядке для повышения его возможности поиска. Проще говоря, данные сортируются так, чтобы их можно было легко найти.
Сравнительная таблица
| Основа для сравнения | Сортировка вставки | Выбор сортировки |
|---|---|---|
| основной | Данные сортируются путем вставки данных в существующий отсортированный файл. | Данные сортируются путем выбора и размещения последовательных элементов в отсортированном месте. |
| Природа | стабильный | неустойчивый |
| Процесс, которому нужно следовать | Элементы известны заранее, в то время как местоположение, чтобы разместить их, ищется. | Местоположение ранее известно, пока элементы ищутся. |
| Немедленные данные | Сортировка вставок - это метод сортировки в реальном времени, который может работать с непосредственными данными. | Он не может иметь дело с непосредственными данными, он должен присутствовать в начале. |
| Наилучшая сложность | На) | O (n 2 ) |
Определение вставки сортировки
Вставка сортировки работает путем вставки набора значений в существующий отсортированный файл. Он создает отсортированный массив, вставляя по одному элементу за раз. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован в некотором порядке. Основная концепция сортировки при вставке состоит в том, чтобы вставить каждый элемент в соответствующее место в окончательном списке. Метод сортировки вставками экономит эффективный объем памяти.
Работа типа вставки
- Он использует два набора массивов, где один хранит отсортированные данные, а другой - в несортированных данных.
- Алгоритм сортировки работает, пока в несортированном наборе нет элементов.
- Давайте предположим, что в массиве есть «n» числовых элементов. Первоначально элемент с индексом 0 (LB = 0) существует в отсортированном наборе. Остальные элементы находятся в несортированном разделе списка.
- Первый элемент несортированной части имеет индекс массива 1 (если LB = 0).
- После каждой итерации он выбирает первый элемент несортированного раздела и вставляет его в нужное место в отсортированном наборе.
Преимущества типа вставки
- Легко реализуется и очень эффективно при использовании с небольшими наборами данных.
- Дополнительное пространство памяти для вставки сортировки меньше (т. Е. O (1)).
- Он считается живым методом сортировки, поскольку список можно сортировать по мере поступления новых элементов.
- Это быстрее, чем другие алгоритмы сортировки.
Пример :
Определение сортировки выбора
Сортировка выбора выполняет сортировку путем поиска номера минимального значения и размещения его в первой или последней позиции в соответствии с порядком (по возрастанию или по убыванию). Процесс поиска минимального ключа и его размещения в правильном положении продолжается до тех пор, пока все элементы не будут расположены в правильном положении.
Работа селекционной сортировки
- Предположим, массив ARR с N элементами в памяти.
- В первом проходе ищется наименьший ключ вместе с его положением, затем ARR [POS] заменяется на ARR [0]. Поэтому ARR [0] сортируется.
- Во втором проходе снова определяется позиция наименьшего значения в подмассиве элементов N-1. Поменяйте местами ARR [POS] с ARR [1].
- На этапе N-1 выполняется тот же процесс для сортировки числа N элементов.
Пример :
Ключевые различия между сортировкой вставок и сортировкой выбора
- Сортировка вставки обычно выполняет операцию вставки. Наоборот, сортировка выбора осуществляет выбор и позиционирование требуемых элементов.
- Сортировка вставок называется стабильной, тогда как сортировка выбора не является устойчивым алгоритмом.
- В алгоритме сортировки вставкой элементы ранее известны. В отличие от сортировки выбора заранее содержит местоположение.
- Сортировка вставкой - это метод оперативной сортировки, при котором поступающие элементы немедленно сортируются в списке, тогда как сортировка выбора не может хорошо работать с непосредственными данными.
- В лучшем случае сортировка вставки имеет время выполнения O (n). В отличие от этого, лучший вариант сложности сортировки во время выполнения - O (n2).
Сложность вставки сортировки
В лучшем случае сложность вставки сортировки составляет O (n) раз, т.е. когда массив был предварительно отсортирован. Таким же образом, когда массив сортируется в обратном порядке, первый элемент несортированного массива сравнивается с каждым элементом в отсортированном наборе. Таким образом, в худшем случае время выполнения сортировки вставкой является квадратичным, т. Е. O (n2) . В среднем случае он также должен провести минимальные (k-1) / 2 сравнения. Следовательно, средний случай также имеет квадратичное время O (n2).
Сложность селекционной сортировки
Что касается работы выбора, сортировка не зависит от исходного порядка элементов в массиве, поэтому нет большой разницы между сложностью выбора в лучшем и худшем случаях.
Сортировка выбора выбирает элемент минимального значения, в процессе выбора сканируется все n элементов; поэтому n-1 сравнения сделаны в первом проходе. Затем элементы взаимозаменяемы. Аналогично, во втором проходе также для поиска второго наименьшего элемента нам требуется сканирование остальных n-1 элементов, и процесс продолжается до сортировки всего массива.
Таким образом, сложность времени выполнения сортировки выбора составляет O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
Заключение
Среди обоих алгоритмов сортировки вставка сортировки быстрая, эффективная, стабильная, в то время как сортировка выбора работает эффективно только тогда, когда задействован небольшой набор элементов или список предварительно частично отсортирован. Количество сравнений, выполненных сортировкой выбора, больше, чем выполняемые перемещения, тогда как при вставочной сортировке количество перемещений или замен элементов больше, чем выполненных сравнений.
