Bubble Sort vs Selection Sort
Bubblesort er en sorteringsalgoritme som fungerer ved å gå gjennom listen for å bli sortert gjentatte ganger mens man sammenligner par av elementer som er tilstøtende. Hvis et par elementer er i feil rekkefølge, byttes de for å plassere dem i riktig rekkefølge. Denne gjennomgangen gjentas inntil det ikke er nødvendig med flere bytter. Utvalgssortering er også en sorteringsalgoritme, som starter med å finne minimumselementet i listen og bytte det med det første elementet. Denne prosessen gjentas for resten av listen ved å plassere byttede elementer i rekkefølge.
Hva er Bubble Sort?
Bubblesort er en sorteringsalgoritme som fungerer ved å gå gjennom listen for å bli sortert gjentatte ganger mens man sammenligner par av elementer som er tilstøtende. Hvis et par elementer er i feil rekkefølge, byttes de for å plassere dem i riktig rekkefølge. Denne gjennomgangen gjentas inntil det ikke er nødvendig med flere bytter (noe som betyr at listen er sortert). Siden de mindre elementene i listen kommer til toppen når en boble kommer til overflaten, får den navnet boblesortering. Boblesortering er en veldig enkel sorteringsalgoritme, men den har en gjennomsnittlig sakstidskompleksitet på O(n2) når du sorterer en liste med n elementer. På grunn av dette er ikke boblesortering egnet for sortering av lister med et stort antall elementer. Men på grunn av sin enkelhet, læres boblesortering under introduksjoner til algoritmer.
Hva er utvalgssortering?
Selection sort er også en annen sorteringsalgoritme som starter med å finne minimumselementet i listen og bytte det med det første elementet. Deretter blir minimumselementet funnet fra resten av listen (fra det andre elementet til det siste elementet i listen) og byttet med det andre elementet. Denne prosessen gjentas for resten av listen ved å plassere byttede elementer i rekkefølge. Så i utvalgssortering, på et hvilket som helst trinn i algoritmen, er listen delt inn i to deler der den ene delen inneholder sorterte elementer og den andre delen inneholder usorterte elementer. Etter hvert som algoritmen fortsetter, vokser den sorterte listen fra venstre til høyre. Utvalgssortering har også en gjennomsnittlig sakstidskompleksitet på O(n2). Derfor egner den seg heller ikke til å sortere store lister.
Hva er forskjellen mellom boblesortering og utvalgssortering?
Selv om både boblesorterings- og seleksjonssorteringsalgoritmene har gjennomsnittlig sakstidskompleksitet O(n2), blir boblesorteringen nesten hele tiden bedre enn seleksjonssorteringen. Dette er på grunn av antallet bytter som trengs av de to algoritmene (boblesorteringer trenger flere bytte). Men på grunn av enkelheten med boblesortering, er kodestørrelsen veldig liten. Stabilitet er en annen forskjell i disse to algoritmene. En stabil sorteringsalgoritme er en sorteringsalgoritme som beholder rekkefølgen på poster hvis listen inneholder elementer med lik verdi. Slik sett er ikke utvalgssortering en stabil algoritme, mens boblesortering er en stabil algoritme.
