Сортиране на вмъкване в JavaScript - Пълно ръководство за сортиране на вмъкване в JavaScript

Въведение в сортирането на вмъкване в JavaScript

Сортирането е едно от важните понятия, които програмистите се учат да започнат своето пътуване в компютърните науки, независимо от езика за програмиране, избран да учи. Сортирането ни помага да намерим целевите данни, които искаме да търсим, по-бързо и удобно, като ги сортираме във възходящ или низходящ ред.

Алгоритмите за сортиране се използват за пренареждане на елементи, където елемент може да бъде число или низ. Има много видове алгоритми за сортиране, базирани на техния метод за сортиране и подхода, който следват за сортиране на елементите, и всеки тип има своите предимства и недостатъци.

В този блог ще се съсредоточим върху сортирането на вмъкване, често срещан вид, който е лесен за разбиране и изпълнение.

Какво е сортиране на вмъкване в JavaScript?

Сортирането на вмъкване е прост, лесен за разбиране алгоритъм, който работи най-добре с малък списък с данни, като сортира всеки елемент от списъка с данни един по един от ляво на дясно. Той е известен и като сортиране за сравнение, където сравнява текущата стойност с останалите стойности в същия списък с данни, който е сортиран. Следва итеративен подход за поставяне на всеки елемент в правилния ред в списъка с данни.

Колкото повече време отнема алгоритъм за сортиране, се казва, че неговата ефективност е лоша и трябва да се обмисли друг алгоритъм, за да се сортират данните. Сортирането на вмъкване има сложност на време O (n²) или изпълнява квадратично време за сортиране на списъка с данни в най-лошия сценарий. Обикновено това не е много ефективно и не трябва да се използва за големи списъци. Обикновено обаче той превъзхожда усъвършенстваните алгоритми като quicksort или mergesort в по-малки списъци.

Сортиране на вмъкване, през повечето време е по-ефективно от други квадратични алгоритми за сортиране, като сортиране на балончета или сортиране на селекция. Най-добрият му сценарий, времето е 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 за контури, външният за цикъл е да повтори елементите на масива, а вътрешният за цикъл се използва за сортиране на елементите на масива във възходящия ред на тяхната стойност. Текущата променлива притежава текущата стойност на масива, а променливата 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)

Външният за итерация на цикъл започва от 1- ^ва позиция на индекса, тъй като искаме да преместим най-малкия елемент в лявата страна, така че сравняваме дали текущият елемент е по-малък от елементите от лявата му страна.

Видове сортиране

Видовете алгоритми, които се използват за сортиране на данни, обхващат следните концепции или идеи в подхода си за сортиране на данните:

Сравнение със стратегии, базирани на несравнение,
Итеративно спрямо рекурсивно изпълнение,
Парадигма за разделяне и завладяване (тази или онази),
Randomize подход.

Нека разгледаме няколко примера:

1. Сливането сортиране използва подход разделяне и завладяване за сортиране на елементи в масив.

2. Сортиране на вмъкване, Сортиране на балоните е сортиран на базата на сравнение.

Когато се сортират данни, става по-лесно да се намери оптимално решение на сложни проблеми. например,

Търсене на конкретна стойност,
Намиране на минималната или максималната стойност,
Тестване за уникалност и изтриване на дубликати,
Преброяване колко пъти се е появила конкретна стойност и т.н.

заключение

В тази статия сме преминали през дефиницията на сортирането на вмъкване и неговата сложност на времето и различни други видове алгоритми за сортиране въз основа на техния подход. Изучаването на различни алгоритми за сортиране ни помага да идентифицираме кой е по-подходящ при определени обстоятелства или да използваме случаи, които ни помагат да сортираме данните с по-бърза скорост.

Препоръчителни статии

Това е ръководство за сортиране на вмъкване в JavaScript. Тук обсъждаме какво е сортиране на вмъкване в JavaScript и неговите типове с пример. Можете също да разгледате следните статии, за да научите повече -