Сегодня мы обсудим алгоритм сортировки, известный как сортировка вставками. Когда я впервые начал свой путь программирования, я думал, что смогу обойтись без глубокого погружения в такие темы, как шаблоны проектирования и алгоритмы. Вскоре я понял, что эти темы не только важны, но и очень полезны, когда дело доходит до более глубокого понимания написания кода. Так зачем изучать алгоритмы? В программировании алгоритмы имитируют реальные жизненные проблемы и предлагают реальные решения этих проблем. Алгоритмы не только помогают углубить ваше понимание написания кода, но и помогают решать распространенные проблемы, с которыми вы столкнетесь при создании приложений. Это отличные умственные упражнения, и они заставляют вас планировать заранее, прежде чем погрузиться прямо в ваш код. Давайте рассмотрим распространенный алгоритм сортировки — алгоритм сортировки вставками.
Что такое алгоритм сортировки вставками?
Алгоритм сортировки вставками — это алгоритм, используемый для сортировки списка элементов в порядке возрастания или убывания. Алгоритм работает аналогично тому, как кто-то, играя в карты, сортирует свои карты. Он работает путем сравнения текущего элемента с элементами слева от него. Если текущий элемент определен как больший, чем элемент слева от него, он вставит текущий элемент перед меньшим элементом.
Шаг за шагом
- Предположим, что первый элемент уже на месте
- Выберите следующий элемент в списке
- Сравните со всеми элементами в отсортированном подсписке (все элементы слева от него)
- Сдвинуть все элементы в отсортированном подсписке, которые больше, чем текущий элемент
- Вставьте значение в список, где элемент слева меньше, а элемент справа больше
- Повторяйте, пока список не будет отсортирован
Когда следует использовать алгоритм сортировки вставками?
Чтобы определить, когда следует использовать этот алгоритм, мы должны взглянуть на его временную сложность. В лучшем случае временная сложность этого алгоритма будет O(n), линейная временная сложность. Это происходит только в том случае, если список, проходящий через алгоритм, уже находится в правильном порядке. В худшем случае временная сложность этого алгоритма равна O(n²), квадратичной временной сложности. Это произойдет, если элементы будут перемешаны, или если они будут полностью в обратном порядке, как мы хотим.
Это означает, что этот алгоритм следует использовать только с меньшими наборами данных, потому что алгоритм с квадратичной временной сложностью может занять очень много времени при работе с большими наборами данных. Однако с небольшими наборами данных этот алгоритм работает быстро, эффективно и очень легко реализуется.
Как использовать алгоритм сортировки вставками?
Я хотел бы продемонстрировать этот алгоритм с помощью Javascript. Взгляните на код ниже, чтобы увидеть мой пример.
const insertionSort = (arr) => {
// determine the length of the input
let len = arr.length;
// iterate through the array
for (var i = 1; i < len; i++) {
// save the current element we are evaluating
let current = arr[i];
// determine the index of the previous element
let j = i - 1;
// while the index of the previous element is greater than -1 (beginning of the list)
// and the current element is less than the previous element
// swap the elements and decrease j by 1
while ((j > -1) && (current < arr[j])) {
// swap
arr[j + 1] = arr[j];
j--;
};
// swap
arr[j+1] = current;
};
return arr;
};
Большой! У нас есть алгоритм, давайте убедимся, что он работает.
let nums = [5,23,54,7,87,2,4,32,8,56,98,43,45,12,21,69,36,25]; console.log(insertionSort(nums)); // [2, 4, 5, 7, 8, 12, 21, 23, 25, 32, 36, 43, 45, 54, 56, 69, 87, 98]
После обработки нашего массива nums алгоритмом insertionSort мы получаем отсортированный массив.
Заключение
В этой статье мы обсудили алгоритм сортировки вставками. Мы обсудили, что такое алгоритм, как он работает, и определили, когда мы должны и не должны его использовать. Надеюсь, вам понравилась эта статья, и вы даже узнали что-то новое! Продолжайте учиться и удачного кодирования!
