…потому что иногда нужно просто рассортировать вещи по старинке.
В прошлый раз, когда мы тусовались с Bubble Sort, вечеринка была… ну, скажем так, немного скучной.
Но не бойтесь, потому что сегодня мы сходим с ума с сортировкой вставками! Это как чуть более крутой и эффективный двоюродный брат Bubble Sort, который знает, как хорошо провести время.
Конечно, это может быть не самый быстрый или причудливый алгоритм сортировки, но иногда вам просто нужно, чтобы он был простым и отсортированным. Итак, возьмите напиток и давайте посмотрим, что такое сортировка вставками!
Что такое сортировка вставками?
Сортировка вставками — это простой алгоритм сортировки, более эффективный, чем сортировка пузырьком.
Он работает, перебирая массив и перемещая элементы в их правильные позиции по одному.
Несмотря на то, что временная сложность в наихудшем случае составляет O(n²), сортировка вставками почти во всех случаях работает лучше, чем пузырьковая сортировка, что делает ее более практичным выбором для сортировки массивов малого и среднего размера.
Как это работает
Давайте рассмотрим, как работает сортировка вставками. Рассмотрим следующий набор букв: E, B, D, A, C.
Чтобы отсортировать эту коллекцию в алфавитном порядке с помощью сортировки вставками, мы должны начать со сравнения второго элемента «B» с первым элементом «E». Так как «B» меньше, чем «E», мы меняем их местами, в результате чего получается набор «B, E, D, A, C».
Далее сравниваем третий элемент «D» со вторым элементом «E». Так как «D» меньше, чем «E», мы меняем их местами, в результате чего получается набор «B, D, E, A, C».
Продолжаем этот процесс, сравнивая четвертый элемент «А» с третьим элементом «Е». Поскольку «А» меньше, чем «Е», мы меняем «А» на «Е», затем сравниваем «А» с «D», «В» и «С», чтобы найти для него правильную позицию.
Наконец, мы сравниваем последний элемент «C» с предыдущими элементами и перемещаем его в правильную позицию в отсортированной коллекции. Окончательная отсортированная коллекция — это «A, B, C, D, E».
Вот PHP-реализация сортировки вставками:
<?php
function insertionSort($arr) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j = $j - 1;
}
$arr[$j + 1] = $key;
}
return $arr;
}
// Example usage
$arr = array(5, 3, 8, 4, 2);
echo "Unsorted array: ";
echo implode(", ", $arr);
echo "\n";
// output
// Unsorted array: 5, 3, 8, 4, 2
$arr = insertionSort($arr);
echo "Sorted array: ";
echo implode(", ", $arr);
echo "\n";
// output
// Sorted array: 2, 3, 4, 5, 8
Сортировка вставками имеет такую же временную сложность O(n²) в наихудшем случае, как и пузырьковая сортировка, что означает, что по мере роста размера коллекции количество времени, необходимое для сортировки коллекции, растет с экспоненциальной скоростью.
Однако на практике сортировка вставками может быть более эффективной, чем пузырьковая сортировка, для небольших коллекций, поскольку для каждого элемента требуется только один обмен.
Это полезно?
Ну, в отличие от пузырьковой сортировки, сортировка вставками может быть весьма полезна в определенных сценариях, особенно при сортировке небольших или частично отсортированных коллекций, поскольку ее временная сложность немного лучше, чем у пузырьковой сортировки.
Сортировка вставками также является хорошим алгоритмом для изучения теми, кто изучает алгоритмы сортировки, поскольку она обеспечивает четкий и интуитивно понятный подход к сортировке. Это особенно полезно для студентов, которые переходят от простых к более сложным алгоритмам.
Например, он часто используется в онлайн-сортировке, когда новые элементы добавляются в коллекцию по одному, а коллекция должна оставаться отсортированной.
Однако для больших коллекций определенно существуют более сильные алгоритмы сортировки, которые могут выполнить работу быстрее, чем вы успеете сказать «сортировка вставками». Как мы упоминали в предыдущей статье, такие алгоритмы, как сортировка слиянием и быстрая сортировка, гораздо более эффективны при работе с большими коллекциями.
Что дальше?
В нашем путешествии по алгоритмам сортировки мы рассмотрели некоторые из самых медленных из них. Теперь мы подходим к последнему из медленных алгоритмов сортировки — сортировке выбором.
Как только мы изучим сортировку выбором, мы, наконец, погрузимся в мир более быстрых алгоритмов сортировки. Эти более быстрые алгоритмы могут более эффективно обрабатывать большие коллекции и широко используются в современных компьютерных системах.
Познакомьтесь с другими алгоритмами сортировки из этой серии
