Введение в сортировку вставок в JavaScript
Сортировка является одним из важных понятий, которые программисты учат начинать свой путь в информатике, независимо от языка программирования, выбранного для изучения. Сортировка помогает нам находить целевые данные, которые мы хотим искать, быстрее и удобнее, сортируя их в порядке возрастания или убывания.
Алгоритмы сортировки используются для изменения порядка элементов, где элемент может быть числом или строкой. Существует много типов алгоритмов сортировки, основанных на их методе сортировки и подходе, который они применяют для сортировки элементов, и каждый тип имеет свои преимущества и недостатки.
В этом блоге мы сконцентрируемся на типе вставок, который легко понять и реализовать.
Что такое вставка сортировки в JavaScript?
Сортировка вставок - это простой и понятный алгоритм, который лучше всего работает с небольшим списком данных, сортируя каждый элемент в списке данных по одному слева направо. Он также известен как сортировка сравнения, где он сравнивает текущее значение с другими значениями в том же списке данных, который сортируется. Следует итеративный подход для размещения каждого элемента в правильном порядке в списке данных.
Чем больше времени занимает алгоритм для сортировки, тем хуже его производительность и что для сортировки данных необходимо рассмотреть другой алгоритм. Сортировка вставок имеет временную сложность O (n²) или выполняет квадратичное время для сортировки списка данных в худшем случае. Это обычно не очень эффективно и не должно использоваться для больших списков. Однако он обычно превосходит усовершенствованные алгоритмы, такие как быстрая сортировка или сортировка слиянием в меньших списках.
Сортировка вставками в большинстве случаев более эффективна, чем другие алгоритмы квадратичной сортировки, такие как пузырьковая сортировка или выборочная сортировка. В лучшем случае это время O (n) или линейное, которое происходит, если входной массив уже отсортирован. В среднем время выполнения вставки сортировки остается квадратичным.
В приведенном ниже примере у нас будет простой высокоуровневый подход для сортировки данных, хранящихся в структуре данных массива, и использование его метода сортировки для сортировки данных без реализации каких-либо алгоритмов.
Пример - вставной алгоритм сортировки
Код:
// Declaring unsorted data and storing it in array data structure
var dataArray = (96, 5, 42, 1, 6, 37, 21) // Function - Insertion Sort Algo.
function insertSort(unsortedData) (
for (let i = 1; i < unsortedData.length; i++) (
let current = unsortedData(i);
let j;
for(j=i-1; j >= 0 && unsortedData(j) > current;j--) (
unsortedData(j + 1) = unsortedData(j) )
unsortedData(j + 1) = current;
)
return unsortedData;
)
// print sorted array
console.log(insertSort(dataArray));
Выход:
Объяснение: В алгоритме мы реализовали 2 цикла for, внешний цикл for предназначен для перебора элементов массива, а внутренний цикл for используется для сортировки элементов массива в порядке возрастания их значения. Текущая переменная содержит текущее значение массива, а переменная j установлена на одно значение меньше текущей позиции индекса массива. Мы проверяем, меньше ли текущий элемент (current), чем значение массива в j- й позиции (unsortedData (j) ), и, если оно истинно, мы сортируем эти значения.
Итерация 1 - текущая (96): (96, 5, 42, 1, 6, 37, 21)
Итерация 2 - текущая (5): (5, 96, 42, 1, 6, 37, 21)
Итерация 3 - текущая (42): (5, 42, 96, 1, 6, 37, 21)
Итерация 4 - текущая (1): (1, 5, 42, 96, 6, 37, 21)
Итерация 5 - текущая (6): (1, 5, 6, 42, 96, 37, 21)
Итерация 6 - текущая (37): (1, 5, 6, 37, 42, 96, 21)
Итерация 7 - текущая (21): (1, 5, 6, 21, 37, 42, 96)
Внешняя итерация цикла for начинается с 1- й позиции индекса, поскольку мы хотим переместить наименьший элемент в левую часть, поэтому мы сравниваем, меньше ли текущий элемент, чем элементы в его левой части.
Типы сортировки
Типы алгоритмов, которые используются для сортировки данных, включают в себя следующие концепции или идеи в их подходе к сортировке данных:
- Сравнение против несопоставимых стратегий,
- Итеративная и рекурсивная реализация,
- Парадигма «разделяй и властвуй» (та или иная),
- Рандомизированный подход.
Давайте рассмотрим несколько примеров:
1. Сортировка слиянием использует подход «разделяй и властвуй» для сортировки элементов в массиве.
2. Вставка сортировки, Bubble Sort - сортировка на основе сравнения.
Когда данные сортируются, становится проще найти оптимальное решение сложных проблем. например,
- Поиск определенного значения,
- Нахождение минимального или максимального значения,
- Тестирование на уникальность и удаление дубликатов,
- Подсчет, сколько раз появилось определенное значение и т. Д.
Вывод
В этой статье мы рассмотрели определение типа вставки и его временную сложность, а также различные другие типы алгоритмов сортировки на основе их подхода. Изучение различных алгоритмов сортировки помогает нам определить, какой из них лучше подходит при определенных обстоятельствах или случаях использования, которые помогают нам сортировать данные с большей скоростью.
Рекомендуемые статьи
Это руководство по сортировке вставок в JavaScript. Здесь мы обсуждаем, что такое вставка сортировки в javascript и ее типы с примером. Вы также можете посмотреть следующие статьи, чтобы узнать больше -
- Шаблоны в JavaScript
- Положение в JavaScript
- Условные выражения в JavaScript
- JavaScript объекты
- Различные типы петель с их преимуществами