Een ander aanzienlijk verschil tussen de twee is dat bellensortering een stabiel algoritme is, terwijl selectiesortering een onstabiel algoritme is. Een algoritme wordt beschouwd als een constante waarbij de elementen met dezelfde sleutel voorkomen in dezelfde volgorde waarin ze plaatsvonden voordat ze in de lijst of array werden gesorteerd. Over het algemeen gebruiken de meeste stabiele en snelle algoritmen extra geheugen.
Vergelijkingstabel
| Basis voor vergelijking | Bubble sorteren | Selectie sorteren |
|---|---|---|
| basis- | Aangrenzend element wordt vergeleken en verwisseld | Het grootste element wordt geselecteerd en verwisseld met het laatste element (in geval van oplopende volgorde). |
| Beste case-time complexiteit | Op) | O (n 2 ) |
| rendement | Inefficiënt | Verbeterde efficiëntie in vergelijking met bubbelsoort |
| Stal | Ja | Nee |
| Methode | uitwisselen | Selectie |
| Snelheid | Langzaam | Snel vergeleken met bubbelsoort |
Definitie van bellen sorteren
Belselectie is het eenvoudigste iteratieve algoritme dat wordt uitgevoerd door elk item of element te vergelijken met het item ernaast en deze zo nodig te verwisselen. In eenvoudige bewoordingen vergelijkt het het eerste en tweede element van de lijst en wisselt het uit, tenzij ze buiten de specifieke volgorde vallen. Evenzo worden het tweede en derde element vergeleken en omgewisseld, en dit vergelijken en omwisselen gaan door tot het einde van de lijst. Het aantal vergelijkingen in de eerste iteratie is n-1, waarbij n de nummerelementen in een array is. Het grootste element bevindt zich op de n-de positie na de eerste iteratie. En na elke iteratie neemt het aantal vergelijkingen af en is er ten slotte slechts één vergelijking.
Dit algoritme is het langzaamste sorteeralgoritme. De beste casuscomplexiteit (wanneer de lijst in de juiste volgorde staat) van het type Bubble is van de orde n ( O (n) ) en de ergste complexiteit is O (n2) . In het beste geval is het van orde n omdat het alleen de elementen vergelijkt en niet verwisselt. Deze techniek vereist ook extra ruimte om de tijdelijke variabele op te slaan.
Definitie van selectiesortering
Selectie sorteren heeft iets betere prestaties bereikt en is efficiënter dan het algoritme voor bellen sorteren. Stel dat we een array in oplopende volgorde willen rangschikken, dan werkt het door het grootste element te vinden en uit te wisselen met het laatste element, en het volgende proces op de subarrays te herhalen tot de hele lijst is gesorteerd.
Belangrijkste verschillen tussen bellen sorteren en selectie sorteren
- Bij de bubbelsoort worden elk element en het aangrenzende element vergeleken en indien nodig verwisseld. Aan de andere kant, selectie sorteren werkt door het element te selecteren en dat specifieke element met het laatste element te verwisselen. Het geselecteerde element kan het grootst of kleinste zijn, afhankelijk van de volgorde, dwz oplopend of aflopend.
- De worst case-complexiteit is hetzelfde in beide algoritmen, dwz O (n2), maar de beste complexiteit is anders. Bellen sorteren neemt een volgorde van n tijd in beslag, terwijl selectie sorteren een orde van n2 tijd verbruikt.
- Luchtbellen sorteren is een stabiel algoritme, daarentegen is selectie sorteren onstabiel.
- Het selectie-sorteeralgoritme is snel en efficiënt in vergelijking met bellensortering, die erg traag en inefficiënt is.
Conclusie
Het algoritme voor bobbelsortering wordt beschouwd als het meest eenvoudige en inefficiënte algoritme, maar het algoritme voor het sorteren van selecties is efficiënt in vergelijking met bellen sorteren. Bubble sorteren verbruikt ook extra ruimte voor het opslaan van tijdelijke variabele en heeft meer swaps nodig.
