Увод у сортирање спајања у ЈаваСцрипт-у
Алгоритми за сортирање су веома важни у рачунарској науци. Резултат сортирања је распоређивање елемената листе према одређеном редослиједу (узлазно или силазно). Спајање сортирања у ЈаваСцрипт-у један је од најефикаснијих алгоритама за сортирање који је доступан јер се заснива на концепту подела и освајања. Као што име говори, прво поделите већи проблем на мале проблеме него решите мање проблеме да бисте решили већи проблем. У концептуалном смислу, Спајање врста је комбинација два основна алгоритма која се зове МЕРГЕ и МЕРГЕ_СОРТ.
која функционише на следећи начин:
- Поделите несврстани списак на н број под-листа са једном ставком (н је укупан број елемената у несортираном списку).
- Подпописе непрестано спајајте у поређане пописи док не постоји само једна сортирана листа.
Имплементација сортирања спајања у ЈаваСцрипт-у
МЕРГЕ алгоритам следи поступак комбиновања две сортиране листе у једну сортирану листу.
Пример: Претпоставимо да постоје две листе, тј. Листа 1 (1, 5, 3) и Листа 2 (7, 2, 9).
1. Прво сортирајте обе листе.
Сада ћемо видети и применити технику Е на њој.
2. Затим ћемо креирати нову листу величине к + и где је к број елемената у Листи 1, а и је број елемената у листи 2.
У нашем случају к = 3 и и = 3, па је к + и = 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)
Алгоритам МЕРГЕ_СОРТ дели задани несортирани списак на минималну величину, а затим позива алгоритам МЕРГЕ да комбинује листу у нову сортирану листу.
Псеудоцоде
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
)
Пример
Овде пратимо имплементацију Спајања сортирања одоздо на доле. Почиње од врха и наставља се према доле, са сваким рекурзивним заокретом поставља исто питање „Шта је потребно учинити да би се листа разврстала?“, А одговор је „Поделите списак на два, извршите рекурзивни позив и спојите резултати ”.
Код у Јавасцрипт-у
// 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
)
Након што смо поставили основни услов за рекурзију, тада ћемо идентификовати средњи индекс да подељену листу поделимо на леву и десну подлистку као што видите горе на примеру дијаграма. Затим требамо спојити леву подлисту и десну потпопису коју ћемо сада гледати. У функцији спајања изнад, морамо се побринути да сортирамо све елементе на левој потпописници и десној подврстиви- листа. Начин на који ћемо то учинити је помоћу петље. У оквиру петље док ћемо поредити елемент у левом потпопису и елемент у десној подврсти један по један. Мањи од два можемо потиснути у листу резултата и према томе померити курсор леве и десне под-листе. На крају, морамо повезати листу резултата. Ово је веома важно! Ако овде не учинимо овај последњи корак, имаћемо непотпун списак елемената на крају, јер услов петље неће успети када било који од два показивача дође до краја.
Излаз:
Својства сортирања спајања
- Разврставање спајања је стабилно јер исти елементи у низу одржавају своје оригиналне положаје у односу једни на друге.
- Разврставање сортирања није „на месту“ јер се током спајања ствара копија целе листе која је сортирана. Због тога је сложеност простора (О (н)) овог алгоритма заправо већа од других, и не треба га користити у сложеним проблемима где је простор врхунски.
- Укупна временска сложеност сортирања Спајања је О (нЛогн). То је ефикасније као иу најгорем случају, време извођења је О (нлогн).
Закључак
Спајање сортирања најбољих, најгорих и просечних временских сложености је исто што га чини ефикаснијим алгоритмом. Делује брже од осталих техника сортирања. Разврставање спајања може се применити на датотеке било које величине. Врло је паралелизабилна због употребе методе подели и освоји. Да бисте развили снажне основе у рачунарској науци, саветујемо вам да темељно разумете различите алгоритме сортирања.
Препоручени чланак
Ово је водич за Спајање сортирања у ЈаваСцрипт-у. Овде смо расправљали о Увођењу сортирања у ЈаваСцрипт и имплементацији заједно са Својствима. Можете и да прођете кроз друге наше предложене чланке да бисте сазнали више -
- ЈаваСцрипт математичке функције
- Увод у ЈаваСцрипт
- Најбољи оквири Јавасцрипт
- ЈаваСцрипт алати
- Топ 6 Алгоритам сортирања у ЈаваСцрипт-у