Inhoud
Het bestellen van een set items in een lijst is een veel voorkomende taak bij het programmeren. Vaak kan een mens deze taak intuïtief uitvoeren. Een computerprogramma moet echter een exacte reeks instructies volgen om het te voltooien, en die reeks wordt een algoritme genoemd. Een ordeningsalgoritme is een methode die wordt gebruikt om een lijst met ongeorganiseerde items in een bepaalde volgorde te plaatsen. De volgorde van bestellen wordt bepaald door een sleutel. Er zijn verschillende sorteeralgoritmen die verschillen in efficiëntie en prestaties. Enkele bekende en belangrijke van dit type zijn: bellen sorteren, selectie sorteren, invoeging sorteren en snel sorteren.
Bubble sorteren
De belsortering wisselt herhaaldelijk aangrenzende elementen uit die niet in orde zijn totdat de volledige lijst met items op volgorde is. Op deze manier zweven de items in de lijst op basis van hun waarden, waarbij de grootste (in het geval van oplopende volgorde) na elke iteratie naar het einde gaat.
Het belangrijkste voordeel van dit algoritme is dat de implementatie ervan eenvoudig en bekend is. Bovendien worden bij de belsoort de elementen van plaats gewisseld zonder gebruik te maken van tijdelijke opslag, waardoor de benodigde ruimte minimaal is. Het grootste nadeel is dat het geen goede resultaten laat zien als de lijst veel items bevat. Dit komt doordat dit type sortering n² verwerkingsstappen vereist voor elk n aantal elementen dat zal worden gesorteerd. Daarom is de bubbelsoort geschikt voor academisch onderwijs, maar niet voor echte toepassingen.
Selectie sorteren
De selectiesortering doorzoekt herhaaldelijk de lijst met items, selecteert één element tegelijk en plaatst het op de juiste positie in de reeks.
Het belangrijkste voordeel van selectiesortering is dat het goed werkt op een korte lijst. Omdat het een algoritme voor plaatsbestelling is, heeft het bovendien geen tijdelijke opslag nodig dan nodig is om de oorspronkelijke lijst op te slaan. Het belangrijkste nadeel is het lage rendement op grote lijsten. Net als bij het sorteren van bellen, vereist het n² aantal stappen voor elk n element. Bovendien worden de prestaties gemakkelijk beïnvloed door de oorspronkelijke volgorde van de items vóór het sorteerproces. Hierdoor is dit selectietype alleen geschikt voor een lijst waar weinig elementen in willekeurige volgorde staan.
Invoegsortering
De invoegsortering scant de lijst herhaaldelijk en voegt telkens een item uit de ongeordende reeks op de juiste positie in.
Het belangrijkste voordeel van sorteren op invoeging is de eenvoud, naast goede prestaties in kleine lijsten. Het is een algoritme voor plaatsbestelling, dus de benodigde ruimte is minimaal. Het nadeel is dat het niet zo goed presteert als andere sorteeralgoritmen. Met n² stappen die nodig zijn om te werken, werkt de invoegsortering ook niet goed met grote lijsten. Het is echter vooral handig bij lijsten met enkele items.
Snel sorteren
Quick sort werkt volgens het principe van verdeeldheid en verovering. Ten eerste verdeelt het de itemlijst in twee sublijsten op basis van een spilelement. Alle elementen in de eerste sublijst zijn zo gerangschikt dat ze kleiner zijn dan het draaipunt, terwijl alle elementen in de tweede sublijst groter zijn gerangschikt dan het draaipunt. Hetzelfde partitionerings- en organisatieproces wordt herhaaldelijk uitgevoerd op de resulterende sublijsten totdat de volledige lijst is georganiseerd.
Snel sorteren wordt door sommigen beschouwd als het beste sorteeralgoritme vanwege het aanzienlijke efficiëntievoordeel, aangezien het goed werkt met een grote lijst met items. Door ter plaatse te bestellen, is er ook geen extra opslagruimte nodig. Het kleine nadeel dat het vertoont, is dat de slechtste prestaties vergelijkbaar zijn met de gemiddelde prestaties van de andere hierboven beschreven algoritmen. Het is echter belangrijk op te merken dat dit ergste geval zeer zeldzaam is. Meer in het algemeen levert snel sorteren de meest efficiënte en meest gebruikte methode op om een lijst van elke omvang te organiseren.
