science >> Wetenschap >  >> anders

De voor- en nadelen van het sorteren van algoritmen

Het sorteren van een set items in een lijst is een taak die vaak voorkomt bij computerprogrammering. Vaak kan een mens deze taak intuïtief uitvoeren. Een computerprogramma moet echter een reeks exacte instructies volgen om dit te bereiken. Deze reeks instructies wordt een algoritme genoemd. Een sorteeralgoritme is een methode die kan worden gebruikt om een lijst met ongeordende items in een geordende volgorde te plaatsen. De volgorde van bestellen wordt bepaald door een sleutel. Er bestaan verschillende sorteeralgoritmen die verschillen in efficiëntie en prestaties. Enkele belangrijke en bekende sorteeralgoritmen zijn de bubbelsortering, de selectiesortering, de invoegsortering en de snelle sortering.
Bubbelsortering

Het bubbelsorteringalgoritme werkt door herhaaldelijk aangrenzende elementen te wisselen die er niet in zitten bestellen totdat de hele lijst met items op volgorde staat. Op deze manier kunnen items worden gezien als borrelend in de lijst op basis van hun sleutelwaarden.

Het primaire voordeel van de bubbelsoort is dat deze populair is en gemakkelijk te implementeren. Bovendien worden in de bubbelsoort elementen op hun plaats geruild zonder extra tijdelijke opslag te gebruiken, dus de benodigde ruimte is minimaal. Het grootste nadeel van de bubbelsoort is het feit dat deze niet goed omgaat met een lijst met een groot aantal items. Dit komt omdat de bubbelsortering n-vierkante verwerkingsstappen vereist voor elk n aantal elementen dat moet worden gesorteerd. Als zodanig is de bubbelsoort meestal geschikt voor academisch onderwijs, maar niet voor praktijktoepassingen.
Selectie sorteren

De selectie sorteren werkt door herhaaldelijk door de lijst met items te gaan, telkens een item te selecteren volgens in de volgorde en het op de juiste positie in de reeks plaatsen.

Het belangrijkste voordeel van de selectie is dat deze goed presteert op een kleine lijst. Omdat het een in-place sorteeralgoritme is, is verder geen extra tijdelijke opslag vereist dan nodig is om de oorspronkelijke lijst te bewaren. Het belangrijkste nadeel van de selectie is de slechte efficiëntie bij het omgaan met een enorme lijst met items. Net als bij de bubbelsortering, vereist de selectiesortering n-vierkant aantal stappen voor het sorteren van n-elementen. Bovendien worden de prestaties ervan gemakkelijk beïnvloed door de eerste bestelling van de artikelen vóór het sorteerproces. Daarom is de selectiesortering alleen geschikt voor een lijst met enkele elementen in willekeurige volgorde.
Invoegsortering

De invoegsortering scant herhaaldelijk de lijst met items, telkens wanneer het item in de ongeordende volgorde in de juiste positie.

Het belangrijkste voordeel van de invoegsoort is de eenvoud. Het vertoont ook goede prestaties bij het omgaan met een kleine lijst. De invoegsortering is een in-place sorteeralgoritme zodat de benodigde ruimte minimaal is. Het nadeel van de invoegsoort is dat deze niet zo goed presteert als andere, betere sorteeralgoritmen. Met n-vierkante stappen vereist voor elk te sorteren n-element, kan de invoegsortering niet goed omgaan met een enorme lijst. Daarom is de invoegsortering vooral handig bij het sorteren van een lijst met enkele items.
Snel sorteren

De snelle sortering werkt volgens het verdeel-en-heers principe. Eerst verdeelt het de lijst met items in twee sublijsten op basis van een pivot-element. Alle elementen in de eerste sublijst zijn gerangschikt om kleiner te zijn dan de pivot, terwijl alle elementen in de tweede sublijst gerangschikt zijn om groter te zijn dan de pivot. Hetzelfde partitionerings- en rangschikproces wordt herhaaldelijk uitgevoerd op de resulterende sublijsten totdat de hele lijst met items is gesorteerd.

De snelle sortering wordt beschouwd als het beste sorteeralgoritme. Dit komt door het grote voordeel op het gebied van efficiëntie omdat het goed kan omgaan met een enorme lijst met items. Omdat het op zijn plaats sorteert, is er ook geen extra opslag vereist. Het kleine nadeel van quick sort is dat de prestaties in het slechtste geval vergelijkbaar zijn met de gemiddelde prestaties van de soorten bubbels, invoegingen of selecties. Over het algemeen produceert de snelle sortering de meest effectieve en meest gebruikte methode om een lijst met elke itemgrootte te sorteren.