En anden betydelig forskel mellem de to er, at boble sorter er stabil algoritme, mens valg sorter er en ustabil algoritme. En algoritme anses for at være stabil, elementerne med den samme nøgle forekommer i samme rækkefølge som de forekom før sortering i listen eller arrayet. Generelt bruger de fleste stabile og hurtige algoritmer ekstra hukommelse.
Sammenligningstabel
| Grundlag for sammenligning | Bubble sort | Valg sort |
|---|---|---|
| Grundlæggende | Tilgrænsende element sammenlignes og bytes | Største element er valgt og byttet med det sidste element (i tilfælde af stigende rækkefølge). |
| Bedste tilfælde tid kompleksitet | På) | O (n2) |
| Effektivitet | ineffektiv | Forbedret effektivitet i forhold til boble sorter |
| stabil | Ja | Ingen |
| Metode | udveksling | Udvælgelse |
| Hastighed | Langsom | Hurtig i forhold til boble sorter |
Definition af boblesort
Bubble sortering er den enkleste iterative algoritme fungerer ved at sammenligne hvert element eller element med elementet ved siden af det og bytte dem om nødvendigt. I enkle ord sammenligner det det første og det andet element i listen og bytter det, medmindre de er ude af en bestemt rækkefølge. Tilsvarende sammenlignes og udskiftes Andet og tredje element, og denne sammenligning og bytte fortsætter til slutningen af listen. Antallet af sammenligninger i den første iteration er n-1, hvor n er talelementerne i en matrix. Det største element ville være på nth position efter den første iteration. Og efter hver iteration falder antallet af sammenligninger og i sidste ende er det kun en sammenligning, der finder sted.
Denne algoritme er den langsomste sorteringsalgoritme. Den bedste tilfælde kompleksitet (når listen er i orden) af typen Bubble er af rækkefølge n ( O (n) ), og værste tilfælde er kompleksiteten O (n2) . I bedste fald er det af rækkefølge n fordi det kun sammenligner elementerne og ikke bytter dem. Denne teknik kræver også ekstra plads til at gemme den midlertidige variabel.
Definition af valg sortering
Valg sort har opnået en smule bedre ydeevne og er effektiv end boble sort algoritme. Antag, at vi vil arrangere en array i stigende rækkefølge, så fungerer den ved at finde det største element og udveksle det med det sidste element, og gentag følgende proces på underarrayerne, indtil hele listen er sorteret.
Nøgleforskelle mellem sortering af bobler og valg af sortering
- I sorten bobles hvert element og dets tilstødende element sammen og byttes om nødvendigt. På den anden side virker sorterings sorter ved at vælge elementet og bytte det pågældende element med det sidste element. Det valgte element kan være størst eller mindste afhængigt af ordren, dvs. stigende eller faldende.
- Det værste tilfælde kompleksitet er det samme i både algoritmerne, dvs. O (n2), men den bedste kompleksitet er anderledes. Bubblesort tager en ordre af n tid, mens sortering sorterer bruger en ordre af n2 tid.
- Bubblesort er en stabil algoritme, derimod er sorterings sort ustabil.
- Valg sort algoritme er hurtig og effektiv i forhold til boble sorter, som er meget langsom og ineffektiv.
Konklusion
Bubble sorteringsalgoritmen anses for at være den mest enkle og ineffektive algoritme, men valg sorteringsalgoritmen er effektiv i forhold til boble sorter. Bubble sort bruger også ekstra plads til opbevaring af midlertidig variabel og har brug for flere swaps.
