Сливане Сортиране в JavaScript - Различни видове имоти

Съдържание:

Anonim

Въведение в сортирането на сливания в JavaScript

Алгоритмите за сортиране са много важни в компютърните науки. Резултатът от сортирането е да подредите елементите от списък в определен ред (възходящ или низходящ). Сливане Сортиране в JavaScript е един от най-ефективните алгоритми за сортиране на разположение, тъй като се основава на концепцията за разделяне и завладяване. Както подсказва името, първо разделете по-големия проблем на малки проблеми, отколкото разрешете по-малките, за да разрешите по-големия проблем. В концептуален план сортирането на сливане е комбинация от два основни алгоритма, наречени MERGE и MERGE_SORT.

който работи както следва:

  1. Разделете несортирания списък на n брой под-списъци с единични елементи (n е общият брой елементи в несортирания списък).
  2. Многократно сливат подлистите в сортирани подлистове, докато има само един сортиран списък.

Прилагане на сортирането на сливания в JavaScript

Алгоритъмът MERGE следва процедурата за комбиниране на два сортирани списъка в един сортиран списък.

Пример: Да предположим, че има два списъка, т.е. списък 1 (1, 5, 3) и списък 2 (7, 2, 9).

1. Първо сортирайте двата списъка.

Сега ще видим и приложим техниката Е върху нея.

2. След това ще създадем нов списък с размер x + y, където x е броят на елементите в Списък 1, а y е броят на елементите в Списък 2.

В нашия случай x = 3 и y = 3, така че x + y = 6.

3. Сега имаме два указателя.
Първи показалец, сочещ към първата позиция на списък 1, и втори показалец, сочещ към първата позиция на списък 2.

4. След това ще сравним стойността на двата указателя. Указателят с по-малка стойност копирайте този елемент в Списък 3 и преместете показалеца вдясно от списъка с по-малка стойност и резултата от списъка (т.е. Списък 1 и Списък 3)

5. По същия начин изпълнете стъпка 4 отново и отново.

По-нататъшно преминаване … ..

Забележка : Ако един от списъците (т.е. списък 1 или списък 2) бъде напълно преминат, както е в случая, след това копирайте цялото съдържание на друг списък от показалеца в списъка с резултати (т.е. списък 3), както следва.

Псевдокод

Function merge (sublist1, sublist2) (
Create var for result list
While sublist1 length > 0 and sublist2 length > 0
If sublist1(0) < sublist2(0) Copy the sublist1 pointer value to result list and Shift pointer of sublist1 to right
else
Copy the sublist2 pointer value to result list and Shift pointer of sublist2 to right
Return concat sublist1 or sublist2 (depending if node1 is empty or not)

Алгоритъмът MERGE_SORT разделя дадения несортиран списък на минимален размер и след това извиква алгоритъма MERGE да комбинира списъка в новия сортиран списък.

Псевдокод

function mergeSort(list) (
If list length < 2
Return list
Create var for middle index of list
Create var for left index of list
Create var for right index of list
Recursively call mergeSort function
)

пример

Тук следваме реализацията на сортиране на сортиране отгоре надолу. Тя започва най-отгоре и продължава надолу, като всеки рекурсивен завой задава един и същ въпрос „Какво е необходимо да се направи, за да се сортира списъкът?“ И отговорът е „Разделете списъка на две, направете рекурсивно повикване и обединете резултати ".

Код в Javascript

// Split the list into halves and merge them recursively
function mergeSort (list) (
if (list.length < 2) (
return list;// return once we hit a list with a single element
)
var mid = Math.floor(list.length / 2);
var left = mergeSort(list.slice(0, mid));
var right = mergeSort(list.slice(mid));
return merge(left, right);
)
// compare the lists element by element and return the concatenated resultList
function merge (sublist1, sublist2) (
var resultList = ();
while (sublist1.length > 0 && sublist2.length > 0)
resultList.push(sublist1(0) < sublist2(0)? sublist1.shift() : sublist2.shift());
return resultList.concat(sublist1.length? sublist1 : sublist2);
)
const list = (6, 5, 3, 1, 8, 7, 2, 4, 2, 5, 1, 2, 3) console.log(mergeSort(list)) //( 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8 )

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

if (list.length < 2) (
return list;// return once we hit a list with a single element
)

След като настроим основното условие за рекурсия, тогава ще идентифицираме средния индекс, за да разделим дадения списък на левия и десния под-списък, както можете да видите по-горе в примерната диаграма. След това трябва да обединим левия под-списък и десния под-списък, който ще разгледаме сега. При функцията за сливане по-горе трябва да се уверим, че сортираме всички елементи в левия под-списък и десния под-списък списък. Начинът, по който ще направим това, е да използваме цикъл за време. В рамките на цикъла while ние ще сравним елемента в левия под-списък и елемента в десния под-списък един по един. Можем да избутаме по-малкия от двете в списъка с резултати и съответно да преместим курсора на левия и десния под-списък. И накрая, трябва да свържем списъка с резултати. Това е много важно! Ако не направим тази последна стъпка тук, ще имаме непълен списък с елементи в края, тъй като условието на цикъл while ще се провали, след като някой от двата указателя достигне края.

изход:

Свойства на сортирането на сливане

  1. Сливането на сортиране е стабилно, тъй като един и същ елемент в масив поддържа първоначалните си позиции по отношение на един друг.
  2. Сливането на сортиране не е „на място“, тъй като по време на сливането се създава копие на целия списък. Поради това пространствената сложност (O (n)) на този алгоритъм всъщност е по-голяма от другите и не трябва да се използва при сложни проблеми, когато пространството е първокласно.
  3. Общата времева сложност на сортирането на Обединяване е O (nLogn). Той е по-ефективен, тъй като е и в най-лошия случай, времето на изпълнение е O (nlogn).

заключение

Обединяване сортиране най-добри, най-лоши и средно сложни времеви сложности са същите, което го прави по-ефективен алгоритъм. Работи по-бързо от другите техники за сортиране. Сливане сортиране може да се приложи към файлове от всякакъв размер. Той е силно паралелен поради използването на метода на разделяне и завладяване. За да развиете силни основи в компютърните науки, ви съветваме да разберете подробно различни алгоритми за сортиране.

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

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

  1. JavaScript математически функции
  2. Въведение в JavaScript
  3. Най-добрите рамки за Javascript
  4. JavaScript инструменти
  5. Топ 6 алгоритъм за сортиране в JavaScript