Beginnersorteringsalgoritmen in JavaScript: Bubble, Selection & Invoegalgoritmen

als uw datasets willekeurig zijn gerangschikt, worden er alleen maar meer tijd en middelen toegevoegd om te beheren en door te zoeken. Of uw gegevens worden gesorteerd of niet zal direct invloed hebben op welke zoekmethoden u kunt gebruiken en kan het verschil betekenen tussen een zoekopdracht die een miljoen bewerkingen of het nemen van 10, zoals bij Binary Search.

omwille van de eenvoud, gaan we ons alleen richten op het sorteren van een array van getallen van minst naar grootste, maar deze algoritmen zijn gemakkelijk te wijzigen voor andere sorteerdoelen. Houd in gedachten dat dit meer algemene concepten en patronen en minder van een “how-to” voor het sorteren van gegevens, omdat uw specifieke implementatie kan veel verschillen, maar op het einde kan conceptueel lijken op deze patronen.

hier is de oefenarray van 50 willekeurige getallen.

const unsortedArr = ;

Prerequisites

ik ga alles bekijken door de lens van de Big O-notatie, dus begrijpen hoe complexiteit in de loop van de tijd toeneemt zal zeer nuttig zijn.

Bubble Sort

Dit is de “Hello World” van sorteermethoden, niets geks, maar het klaart de klus.

voor elk item in de array willen we controleren of het volgende item groter is, als het dan hun indexen in de array verwisselt. Om te voorkomen dat gesorteerde getallen worden aanbevolen, beginnen we aan de achterkant van de array, terwijl een andere for loop het voorgaande nummer krijgt. Op deze manier alle van de grootste waarden opbouwen, of “bubbels up”, op het einde.

Bubble Sorteeranimatie

grafisch / animatie dankzij VisuAlgo.net

onze versie werkt in omgekeerde richting van de animatie, maar het is dichtbij genoeg.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

selectie Sorteren

selectie Sorteren werkt als het tegenovergestelde van Bubble sorteren, terwijl bubble Sorteren alle grootste waarden naar het einde pusht nu gaan we de minimale waarden naar het begin duwen.

elke keer dat het over de array loopt selecteert het de kleinste waarde, als het een lagere waarde vindt die dan de nieuwe laagste waarde wordt. Wanneer de lus is gedaan zal het nemen dat minimum en zet het op de voorkant van de array voor het starten van de lus opnieuw. Op deze manier wordt de laagste waarde van elke iteratie op de voorkant gestapeld totdat de hele array gesorteerd is.

selectie Sorteer animatie

grafische / animatie dankzij VisuAlgo.net

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

Invoegsoort

mijn persoonlijke favoriet en de meest performante van de drie, invoegsoort, lijkt meer op hoe je iets met de hand zou Sorteren.

we kijken naar de array als twee delen, de gesorteerde en ongesorteerde, waarbij elke keer dat we een nieuwe waarde vinden we teruglopen om zijn plaats in de gesorteerde helft te vinden. Met elke toevoeging groeit onze gesorteerde groep tot het de hele array is.

Insertiesorteeranimatie

grafische / animatie dankzij VisuAlgo.net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

vergelijking

een probleem met het gebruik van Big O-notatie voor het vergelijken van algoritmen is dat het gebaseerd is op het slechtere scenario, dat hetzelfde kan zijn tussen algoritmen, wat de valse illusie geeft dat ze gelijk zijn. Terwijl Bubble, selectie en inserties allemaal O(n^2) zijn, vertelt dat ons niet veel over het gemiddelde of beste scenario of hoe ze variëren met de gegevensstructuur.

Invoegsortatie wint elke keer. Het heeft ook het voordeel dat u niet de hele reeks hoeft te hebben voordat u begint, waarmee u dingen in real-time kunt sorteren als gegevens binnenkomen.

houd dit in gedachten omdat u niet moet beslissen welk algoritme “het beste” is voordat u overweegt hoe uw gegevens al zijn georganiseerd.

conclusie

deze drie zijn verre van de beste oplossingen voor het efficiënt sorteren van grote hoeveelheden gegevens, maar ze zijn een van de meest intuïtieve om je tenen te dompelen in wat een overweldigende oceaan kan zijn. 🌊