На этой неделе я собираюсь осветить, как вы догадались! Алгоритмы сортировки! В частности, я буду обсуждать алгоритм сортировки вставкой. Как я упоминал в своем последнем посте, списка Алгоритмы, которые должен знать каждый разработчик программного обеспечения как такового не существует. Однако каждый инженер-программист должен иметь определенный уровень знакомства с алгоритмами. Имейте в виду, что главный вывод этого поста и даже последнего - не запоминать код дословно. Вместо этого нужно помнить логику, используемую для решения указанных алгоритмов. (С вами тоже намного проще!)

Так что же такое алгоритм сортировки вставкой? Это довольно простой алгоритм. Он в основном сортирует массив элементов по порядку, сравнивая каждый элемент с предыдущими элементами и перемещая каждый элемент соответствующим образом. Вот пример. Представьте, что у нас есть массив, подобный нижнему.

let array = [10, 3, 8, 2, 7]

Затем представьте, если бы мы применили функцию сортировки к массиву.

[3, 10, 8, 2, 7] → [3, 8, 10, 2, 7] →[3, 8, 2, 10, 7] → [3, 2, 8, 10, 7] →[2, 3, 8, 10, 7] →[2, 3, 8, 7, 10]

Как показано выше, элементы в массиве будут непрерывно перемешиваться, пока все элементы не будут в порядке. А теперь давайте представим, что мы были на собеседовании и нас просили создать алгоритм сортировки вставками. Зная, что это такое, мы знаем, что алгоритм сортировки вставкой принимает аргумент (который представляет собой массив).

Представьте, что вам дали массив, как в первой строке, простой список произвольных чисел. Строки с 3 по 5 - это только начало того, как мы называем нашу функцию и даем ей аргумент.

Из того, что мы знаем о приведенном выше объяснении того, что такое сортировка вставкой, мы знаем, что нам нужно пройти через все элементы массива или выполнить итерацию через массив. Для этого запустим цикл for.

Теперь у нас есть цикл for! Мы можем перебирать наш массив. Следующий шаг - найти способ сравнить каждый элемент друг с другом.

Мы создали две переменные! У нас есть один для представления текущего элемента в массиве, а другой для представления предшествующего элемента (для сравнения). Теперь нам нужно создать еще один цикл для сравнения двух.

Разберем строку 7. Нам нужно было выполнить определенные условия при сравнении элементов.

  1. j не может быть меньше 0, потому что индексы начинаются с 0, и это вызовет ошибку.
  2. если array [j] больше, чем текущий элемент, о котором идет речь, мы должны переставить элементы в массиве так, чтобы он был отсортирован

Давайте теперь посмотрим на следующую строку, строку 8. Теперь, когда у нас есть условие, соответствующее строке 7, мы должны сделать так, чтобы массив [j] непрерывно перемещался по массиву (мы восстанавливаем j в строке после)

Вот окончательное решение!

let array = [10, 3, 8, 2, 7]
function insertionSort(array) {
 for (let i = 1; i < array.length; i++) {
  let currentElement = array[i];
  let j = i - 1;
  while (j >= 0 && array[j] > currentElement) {
   array[j + 1] = array[j];
   j = j - 1;
  }
  array[j + 1] = currentElement;
 }
 return array;
};

Скопируйте код и попробуйте!

Давайте посмотрим на строку 11. Согласно второму циклу мы создаем array [j + 1] = currentElement, потому что array [j + 1], потому что array [j] соответствует первому элементу в этом массиве. Строка 13 просто возвращает массив, поэтому, когда вы запускаете функцию, она выводит массив, который вы изначально ввели, в отсортированном порядке.

Преимущества

· Подходит для массивов меньшего размера или массивов, которые уже были почти отсортированы

· Очень эффективный

Недостатки

· Может работать медленно, если массив имеет больший размер или элементы в массиве перевернуты (например, array = [20, 17, 13, 8, 3]