Verschil tussen Bubble Sort en Selection Sort
Inhoud
Sorteren is een van de belangrijkste taken in computerprogramma's waarin de elementen van een array in een bepaalde volgorde zijn gerangschikt. Sorteren maakt zoeken eenvoudiger. Bellen sorteren en Selectie sorteren zijn de sorteeralgoritmen die kunnen worden onderscheiden door de methoden die ze gebruiken voor het sorteren. Belsortering wisselt in wezen de elementen uit, terwijl selectiesortering het sorteren uitvoert door het element te selecteren.
Een ander aanzienlijk verschil tussen de twee is dat de bubbelsoort een stabiel algoritme is, terwijl de selectiesoort een onstabiel algoritme is. Een algoritme wordt beschouwd als stabiel waarbij de elementen met dezelfde sleutel voorkomen in dezelfde volgorde als vóór het sorteren in de lijst of array. Over het algemeen gebruiken de meeste stabiele en snelle algoritmen extra geheugen.
- Vergelijkingstabel
- Definitie
- Belangrijkste verschillen
- Gevolgtrekking
Vergelijkingstabel
| Basis voor vergelijking | Bellen soort | Selectie sorteren |
|---|---|---|
| basis- | Aangrenzend element wordt vergeleken en verwisseld | Het grootste element is geselecteerd en verwisseld met het laatste element (in oplopende volgorde). |
| Beste tijd complexiteit | Aan) | Aan2) |
| rendement | Inefficiënt | Verbeterde efficiëntie in vergelijking met bubbelsortering |
| Stal | Ja | Nee |
| Methode | uitwisselen | Selectie |
| Snelheid | Langzaam | Snel in vergelijking met bubbelsortering |
Definitie van Bubble Sort
Bellen soort is het eenvoudigste iteratieve algoritme dat wordt gebruikt door elk item of element te vergelijken met het item ernaast en ze indien nodig te verwisselen. In eenvoudige woorden, het vergelijkt het eerste en tweede element van de lijst en verwisselt het, tenzij ze niet in een specifieke volgorde staan. Evenzo worden het tweede en derde element vergeleken en geruild, en dit vergelijken en ruilen gaat 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 zou na de eerste iteratie op de negende positie staan. En na elke iteratie neemt het aantal vergelijkingen af en uiteindelijk vindt slechts één vergelijking plaats.
Dit algoritme is het langzaamste sorteeralgoritme. De beste case-complexiteit (wanneer de lijst in volgorde is) van de soort Bubble is van orde n (Aan)), en de worst case-complexiteit is Aan2). 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 selectie sorteren
Selectie sorteren heeft iets betere prestaties behaald en is efficiënter dan het soort bubbelsoort. Stel dat we een array in oplopende volgorde willen rangschikken, dan functioneert deze door het grootste element te vinden en het te vervangen door het laatste element, en herhaalt u het volgende proces op de subarrays totdat de hele lijst is gesorteerd.
- In de bubbelsoort worden elk element en het aangrenzende element vergeleken en indien nodig verwisseld. Aan de andere kant werkt selectie sorteren door het element te selecteren en dat specifieke element met het laatste element te verwisselen. Het geselecteerde element kan het grootst of het kleinst zijn, afhankelijk van de volgorde, d.w.z. oplopend of aflopend.
- De complexiteit in het slechtste geval is hetzelfde in beide algoritmen, d.w.z. O (n2), maar de beste complexiteit is anders. Belsortering neemt een volgorde van n tijd aan, terwijl selectie sorteren een volgorde van n gebruikt2 tijd.
- Belsortering is een stabiel algoritme, daarentegen is selectiesoort instabiel.
- Selectie sorteeralgoritme is snel en efficiënt in vergelijking met bubbelsortering die erg langzaam en inefficiënt is.
Gevolgtrekking
Bellen sorteeralgoritme wordt beschouwd als het meest eenvoudige en inefficiënte algoritme, maar selectie sorteeralgoritme is efficiënt in vergelijking met bubbelsortering. Bubbelsoort verbruikt ook extra ruimte voor het opslaan van tijdelijke variabelen en heeft meer swaps nodig.
