Forskellen mellem boble sortering og udvælgelse sortering

Bubble Sort vs Selection Sort

Bubble sort er en sorteringsalgoritme, der fungerer ved at gå gennem listen, der skal sorteres gentagne gange, mens man sammenligner par af elementer, der støder op til hinanden. Hvis et par elementer er i forkert rækkefølge, udskiftes de for at placere dem i den rigtige rækkefølge. Denne gennemgang gentages, indtil der ikke kræves yderligere swaps. Valgsortering er også en sorteringsalgoritme, der starter med at finde minimumselementet på listen og bytte det med det første element. Denne proces gentages for resten af ​​listen ved at placere udskiftede elementer i rækkefølge.

Hvad er Bubble Sort?

Bubble sort er en sorteringsalgoritme, der fungerer ved at gå gennem listen, der skal sorteres gentagne gange, mens man sammenligner par af elementer, der støder op til hinanden. Hvis et par elementer er i forkert rækkefølge, udskiftes de for at placere dem i den rigtige rækkefølge. Denne gennemgang gentages, indtil der ikke kræves yderligere swaps (hvilket betyder, at listen er sorteret). Da de mindre elementer på listen kommer til toppen, når en boble kommer til overfladen, får den navnet boble sortering. Boblesortering er en meget simpel sorteringsalgoritme, men den har en gennemsnitlig sags tidskompleksitet på O (n2), når du sorterer en liste med n elementer. På grund af dette er boble sortering ikke egnet til sortering af lister med et stort antal elementer. Men på grund af sin enkelhed, undervises boble sortering under introduktion til algoritmer.

Hvad er valgssortering?

Valgsortering er også en anden sorteringsalgoritme, der starter med at finde minimumselementet på listen og bytte det med det første element. Derefter findes minimumelementet fra resten af ​​listen (fra det andet element indtil det sidste element på listen) og byttes med det andet element. Denne proces gentages for resten af ​​listen ved at placere udskiftede elementer i rækkefølge. Så i valg af sortering, på ethvert trin i algoritmen, er listen delt i to dele, hvor den ene del indeholder sorterede elementer, og den anden del indeholder usorterede elementer. Når algoritmen fortsætter, vokser den sorterede liste fra venstre til højre. Valgssortering har også en gennemsnitlig sagstidskompleksitet på O (n2). Derfor er det heller ikke egnet til sortering af store lister.

Hvad er forskellen mellem Bubble Sort og Selection Sort?

Selvom både bobelsorterings- og udvælgelsessorteringsalgoritmer har gennemsnitlige sags-tidskompleksiteter på O (n2), er boble-sortering næsten hele tiden bedre end udvælgelsessorteringen. Dette skyldes antallet af swaps, der kræves af de to algoritmer (boble sortering har brug for flere swaps). Men på grund af enkelheden med boble sortering, er dens kodestørrelse meget lille. Stabilitet er en anden forskel i disse to algoritmer. En stabil sorteringsalgoritme er en sorteringsalgoritme, der bevarer rækkefølgen af ​​poster, hvis listen indeholder elementer med en samme værdi. I den forstand er udvælgelsessorter ikke en stabil algoritme, mens boble-sortering er en stabil algoritme.