Flet Sorter i JavaScript - Forskellige typer egenskaber

Indholdsfortegnelse:

Anonim

Introduktion til fletningssortering i JavaScript

Sorteringsalgoritmer er meget vigtige inden for datalogi. Outputet fra sorteringen er at arrangere elementerne i en liste i en bestemt rækkefølge (enten stigende eller faldende). Flet sortering i JavaScript er en af ​​de mest effektive sorteringsalgoritmer, der er tilgængelige, da den er baseret på begrebet kløft og erobrere. Som navnet antyder, skal du først opdele det større problem i små problemer end løse de mindre problemer for at løse det større problem. Konceptuelt er Merge sort en kombination af to grundlæggende algoritmer kaldet MERGE og MERGE_SORT.

der fungerer som følger:

  1. Opdel den usorterede liste i n antal undelister med enkeltelementer (n er det samlede antal elementer i den usorterede liste).
  2. Bland gentagne gange sublister til sorterede sublister, indtil der kun er en sorteret liste.

Implementering af fletningssortering i JavaScript

MERGE-algoritmen følger proceduren for at kombinere to sorterede lister til en sorteret liste.

Eksempel: Antag, at der er to lister, dvs. liste 1 (1, 5, 3) og liste 2 (7, 2, 9).

1. Sorter først begge lister.

Nu vil vi se og anvende E-teknikken på den.

2. Derefter opretter vi en ny liste med størrelse x + y, hvor x er antallet af elementer i liste 1 og y er antallet af elementer i liste 2.

I vores tilfælde x = 3 og y = 3, så x + y = 6.

3. Nu har vi to tip.
En første markør, der peger på den første position på liste 1 og den anden pointer, der peger på den første position på liste 2.

4. Så sammenligner vi værdien af ​​begge pegere. Markøren med mindre værdi, kopier dette element til liste 3 og flyt markøren til højre for listen med mindre værdi og den resulterende liste (dvs. liste 1 og liste 3)

5. Udfør på samme måde trin 4 igen og igen.

Yderligere krydsning… ..

Bemærk : Hvis en af ​​listerne (dvs. liste 1 eller liste 2) bliver gennemgået fuldt ud som i tilfældet, skal du kopiere hele indholdet af en anden liste fra markøren til resultatlisten (dvs. liste 3) som følger.

pseudokode

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-algoritmen opdeler den givne usorterede liste til minimumsstørrelse og kalder derefter MERGE-algoritmen til at kombinere listen i den nye sorterede liste.

pseudokode

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
)

Eksempel

Her følger vi top-down Merge Sort-implementering. Det starter øverst og fortsætter mod nedad, med hver rekursiv drejning, der stiller det samme spørgsmål "Hvad kræves der for at sortere listen?" Og har svaret er "Opdel listen i to, foretage et rekursivt opkald og flet resultater”.

Kode i 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 )

Hovedfunktionen af ​​flettsorteringen vil opdele den givne liste i mindre lister i hver iteration af det rekursive opkald. Glem ikke at rekursion kræver basisbetingelsen for at undgå uendelig rekursion. I vores tilfælde har vi:

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

Når vi har konfigureret basisbetingelsen for rekursion, identificerer vi midtindekset for at opdele den givne liste i venstre og højre undeliste, som du kan se ovenfor i eksemplet. Derefter er vi nødt til at flette den venstre underliste og den højre undeliste, som vi vil se nu. I fusionfunktionen ovenfor skal vi sørge for, at vi sorterer alle elementerne i den venstre underliste og den højre under- liste. Den måde, vi gør dette på, er ved at bruge en stundsløjfe. Inden for loopen vil vi sammenligne elementet i den venstre underliste og elementet i den højre underliste en efter en. Vi kan skubbe den mindste af de to ind i resultatlisten og flytte markøren for den venstre underliste og den højre underliste i overensstemmelse hermed. Endelig er vi nødt til at sammenkæde resultatlisten. Dette er meget vigtigt! Hvis vi ikke gør dette sidste trin her, vil vi have en ufuldstændig liste over elementer i slutningen, fordi status for loop-tilstanden mislykkes, når et af de to pegere når slutningen.

Produktion:

Egenskaber ved fletningssortering

  1. Flettesortering er stabil, da det samme element i en matrix opretholder deres oprindelige positioner i forhold til hinanden.
  2. Flettesortering er ikke 'på plads', da det under sammenlægning skaber en kopi af hele listen sorteres. På grund af dette er rumkompleksiteten (O (n)) af denne algoritme faktisk større end andre, og skal ikke bruges i komplekse problemer, hvor pladsen er premium.
  3. Den samlede tidskompleksitet af flettsortering er O (nLogn). Det er mere effektivt, da det også er i værste tilfælde, runtime er O (nlogn).

Konklusion

Flet sortering af bedste, værste og gennemsnitlige tilfælde er de samme, hvilket gør det til en mere effektiv algoritme. Det fungerer hurtigere end andre sorteringsteknikker. Flettsortering kan anvendes på filer af enhver størrelse. Det er meget paralleliserbart på grund af brugen af ​​divide-and-conquer-metoden. For at udvikle stærke grundlæggende inden for datalogi rådes du til grundigt at forstå forskellige sorteringsalgoritmer.

Anbefalet artikel

Dette har været en guide til Flet sortering i JavaScript. Her diskuterer vi Introduktion til fletningssortering i JavaScript og implementeringen sammen med Egenskaber. Du kan også gennemgå vores andre foreslåede artikler for at lære mere -

  1. JavaScript-matematikfunktioner
  2. Introduktion til JavaScript
  3. Bedste Javascript-rammer
  4. JavaScript-værktøjer
  5. Top 6 sorteringsalgoritme i JavaScript