Ключевая разница - сортировка вставками и сортировка выбором
Сортировка вставками и сортировка выбором - это два алгоритма сортировки, используемые для сортировки набора данных. Иногда необходимо расположить данные в определенном порядке. Алгоритмы сортировки - это механизмы для сортировки набора данных. При сортировке данные располагаются в числовом или лексикографическом порядке. Если данные отсортированы правильно, то поиск данных будет выполняться быстрее. Если телефонные номера в телефонном справочнике не отсортированы, то будет трудно найти конкретный телефонный номер. Точно так же, если слова в словаре расположены не в алфавитном порядке, найти слова будет очень сложно. Поэтому сортировка полезна в повседневной жизни. В компьютерных науках существуют алгоритмы сортировки для сортировки набора данных. Два таких алгоритма - сортировка вставками и сортировка выбором. Сортировка вставками - это алгоритм сортировки, который сортирует массив, перемещая элементы один за другим. Сортировка выбором - это алгоритм сортировки, который находит наименьший элемент в массиве и заменяет элемент на первую позицию, затем находит второй наименьший элемент и заменяет его элементом на второй позиции и продолжает процесс до тех пор, пока весь массив не будет отсортирован.. Основное различие между сортировкой вставками и сортировкой выбором заключается в том, что сортировка вставками сравнивает два элемента за раз, а сортировка выбором выбирает минимальный элемент из всего массива и сортирует его.
Что такое сортировка вставками?
Сортировка вставками - это алгоритм сортировки на основе сравнения на месте. В этом методе массив просматривается поэтапно. Несортированные элементы перемещаются и вставляются в отсортированный подсписок массива. Алгоритм сортировки вставками можно пояснить на следующем примере.
Например, возьмем исходный массив как 77, 33, 44, 11, 88. В этом алгоритме сортировки первым шагом является выбор текущего элемента.
Текущий элемент равен 77. Текущий элемент сравнивается со всеми элементами в левой части. 77 - это первый элемент, и в левой части нет элементов. Индекс текущей позиции равен 0.
Затем индекс текущей позиции увеличивается на 1. Теперь индекс равен 1, а текущий элемент равен 33. При сравнении его с элементом слева он меньше 77. Тогда оба этих значения меняются местами. Теперь 33 находится в индексе 0, а 77 - в индексе 1.
Теперь массив равен 33, 77, 44, 11, 88.
И снова индекс увеличивается. Индекс равен 2, а текущий элемент равен 44. Он сравнивается с элементами в левой части. 44 меньше 77. Таким образом, эти два значения меняются местами. Теперь массив 33, 44, 77, 11, 88. Нужно сравнить все элементы слева. Итак, 44 сравнивается с 33. 33 меньше 44. Таким образом, эти элементы не нужно менять местами.
Теперь массив равен 33, 44, 77, 11, 88.
И снова индекс увеличивается. Индекс равен 3, а текущий элемент равен 11. Он сравнивается со всеми элементами слева. 11 меньше 77, поэтому эти два числа меняются местами. Теперь массив равен 33, 44, 11, 77, 88. При сравнении 11 и 44 11 меньше 44. Таким образом, эти два числа меняются местами. Теперь массивы 33, 11, 44, 77, 88. Опять 11 сравнивается с 33. 11 меньше 33, поэтому эти два значения меняются местами.
Теперь массив равен 11, 33, 44, 77, 88.
Увеличение индекса сделает индекс равным 4. Значение равно 88. Оно больше, чем 77. Таким образом, нет необходимости в обмене. Наконец, отсортированный массив равен 11, 33, 44, 77, 88.
Рисунок 01: Пример сортировки вставками
Реализация сортировки вставками описана выше. Исходный массив был 77, 33, 44, 11, 88. После сортировки он дает на выходе 11, 33, 44, 77, 88.
Что такое сортировка выбором?
Сортировка выбором - это алгоритм сортировки на основе сравнения на месте. Массивы разбиты на секции. Отсортированная часть находится в левом конце. Несортированная часть находится в правом конце. Сначала нужно найти наименьшее значение. Затем он заменяется левым элементом. Теперь этот элемент находится в отсортированном массиве. Этот процесс продолжает перемещать несортированную границу массива от одного элемента вправо. Алгоритм сортировки выбором можно пояснить на следующем примере.
Например, возьмем исходный массив как 77, 33, 44, 11, 88, 22. В этом алгоритме сортировки находится наименьшее в массиве. Наименьший элемент равен 11. Он заменяется элементом в индексе 0 массива.
Теперь массив равен 11, 33, 44, 77, 88, 22.
Наименьший элемент находится в индексе 0, поэтому 11 теперь отсортированы. Из остальных элементов наименьший - 22. Он заменяется на 1st индексный элемент.
Теперь массив равен 11, 22, 44, 77, 88, 33.
Элементы 11 и 22 уже отсортированы. Из остальных наименьшее значение равно 33. Оно заменяется на элемент индекса 2nd.
Теперь массив равен 11, 22, 33, 77, 88, 44.
Элементы 11, 22 и 33 уже отсортированы. Из остальных наименьшее значение равно 44. Оно заменяется на элемент индекса 3rd.
Теперь массив равен 11, 22, 33, 44, 88, 66.
Элементы 11, 22, 33, 44 уже отсортированы. Остальные элементы 88 и 66. Элемент 66 заменяется на элемент индекса 4th.
Теперь массив равен 11, 22, 33, 44, 66, 88.
Это отсортированный массив с использованием алгоритма сортировки выбором.
Рисунок 02: Пример сортировки выбором
Реализация сортировки вставками описана выше. Исходный массив был 77, 33, 44, 11, 88. После сортировки он дает на выходе 11, 33, 44, 77, 88.
В чем сходство между сортировкой вставками и сортировкой выбором?
И сортировка вставками, и сортировка выбором являются алгоритмами сортировки
В чем разница между сортировкой вставками и сортировкой выбором?
Сортировка вставками и сортировка выбором |
|
| Сортировка вставками - это алгоритм сортировки, который сортирует массив, сдвигая элементы один за другим. | Сортировка выбором - это алгоритм сортировки, который находит наименьший элемент в массиве и заменяет элемент на первую позицию, затем находит второй наименьший элемент и заменяет его на элемент на второй позиции и продолжает процесс до тех пор, пока весь массив отсортирован. |
| Процесс | |
| Сортировка вставками заключается в сортировке вложенного списка путем сравнения двух элементов до тех пор, пока не будет отсортирован весь массив. | Сортировка выбором выбирает минимальный элемент и меняет его местами с первой позицией, снова выбирает минимум для остальных и меняет местами на вторую позицию и продолжает этот процесс до конца. |
| Стабильность | |
| Сортировка вставками - это стабильный алгоритм сортировки. | Сортировка выбором не является стабильным алгоритмом сортировки. |
Сводка - сортировка вставками и сортировка выбором
Иногда необходимо отсортировать данные. В компьютерных науках есть алгоритмы для сортировки данных. В этой статье обсуждались два алгоритма сортировки: сортировка вставками и сортировка выбором. Сортировка вставками - это алгоритм сортировки, который сортирует массив, перемещая элементы один за другим. Сортировка выбором - это алгоритм сортировки, который находит наименьший элемент в массиве и заменяет элемент на первую позицию, затем находит второй наименьший элемент и заменяет его элементом на второй позиции и продолжает процесс до тех пор, пока весь массив не будет отсортирован.. Разница между сортировкой вставками и сортировкой выбором заключается в том, что сортировка вставками сравнивает два элемента за раз, а сортировка выбором выбирает минимальный элемент из всего массива и сортирует его.
Загрузить PDF-файл о сортировке вставками и сортировке выбором
Вы можете загрузить PDF-версию этой статьи и использовать ее в автономном режиме в соответствии с примечанием к цитированию. Загрузите PDF-версию здесь: Разница между сортировкой вставками и сортировкой выбором
