Понимание структур данных, алгоритмов и базовых концепций программирования необходимо для того, чтобы стать лучшим разработчиком. В настоящее время большинство этих проблем решается с использованием современных инструментов и библиотек, но более глубокие знания в этой области определенно расширят ваши перспективы разработки программного обеспечения.

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

Что такое сортировка вставкой?

Сортировка вставкой - еще один популярный алгоритм сортировки, хотя он не такой производительный, как, например, быстрая сортировка или сортировка слиянием. Это работает так, что он разбивает массив на две части - отсортированную и несортированную. Мы еще не знаем, находится ли какой-либо из элементов на своем месте, поэтому мы начнем наш отсортированный список с первого элемента (сортируется массив из одного элемента).

Затем мы начинаем перебирать другие элементы в массиве. Для каждого из них мы должны найти подходящее место в отсортированном массиве. Мы делаем это, находя первый меньший элемент или пока не дойдем до начала отсортированного списка. Возможно, будет лучше, если я покажу вам пример того, что на самом деле происходит. Отсортированный массив будет выделен жирным шрифтом.

5, 9, 13, 4, 1, 6 // the only sorted part is the first item
5, 9, 13, 4, 1, 6 // 9 > 5 so we don't move it
5, 9, 13, 4, 1, 6 // 13 > 9 we don't move it
4, 5, 9, 13, 1, 6 // compare all to 4, until we reach the head 
1, 4, 5, 9, 13, 6 // compare all to 1, until we reach the head
1, 4, 5, 6, 9, 13 // first smaller item is 5, place 6 before it

Как это работает?

Особенность сортировки вставкой заключается в том, что мы не меняем местами элементы. Хотя кажется, что мы меняем их местами и перемещаем, на самом деле происходит то, что мы перебираем отсортированную часть, находим первый меньший элемент (или заголовок массива) и помещаем туда наш элемент. Что нам делать с предметами перед этим? Поскольку мы перебираем каждый из них, каждое большее число фактически перемещается на один индекс вперед (ну, не перемещается - копируется), чтобы освободить место для текущего элемента.

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

Как только вы поймете концепцию, перенести ее в код совсем несложно. Я бы сказал, что это один из самых простых алгоритмов для реализации. Потратьте на это немного времени, запишите на листе бумаги, усвоите идею, и кодирование не будет проблемой.

Спасибо за то, что прочитали, если вы ищете больше материалов по информатике, связанных с JS, в настоящее время я пишу о них целую серию статей. Если вам нужен общий JS-контент, вы можете взглянуть на мой профиль.

Программирование с помощью JS:

Рекурсия: https://hackernoon.com/programming-with-js-recursion-31371e2bf808
Сортировка слиянием: https://medium.com / @ KondovAlexander / programming-with-js-merge-sort-deb677b777c0
Двоичный поиск: https://medium.com/@KondovAlexander/programming-with-js-binary- search-aaf86cef9cb3
Сортировка вставки: https://medium.com/@KondovAlexander/programming-with-js-insertion-sort-1316df8354f5