Bubble Sort vs Insertion 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. Innsettingssortering er også en sorteringsalgoritme, som fungerer ved å sette inn et element i inndatalisten til riktig posisjon i en liste som allerede er sortert. Denne prosessen brukes gjentatte ganger til listen er sortert.
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 innsettingssortering?
Innsettingssortering er en annen sorteringsalgoritme, som opererer ved å sette inn et element i inndatalisten til riktig posisjon i en liste (som allerede er sortert). Denne prosessen brukes gjentatte ganger til listen er sortert. Ved innsettingssortering utføres sortering på stedet. Derfor etter iterasjonen av algoritmen, vil de første i+1-oppføringene i listen bli sortert og resten av listen vil være usortert. Ved hver iterasjon vil det første elementet i den usorterte delen av listen bli tatt og satt inn på riktig sted i den sorterte delen av listen. Innsettingssortering har en gjennomsnittlig sakstidskompleksitet på O(n2). På grunn av dette er heller ikke innsettingssortering egnet for sortering av store lister.
Hva er forskjellen mellom boblesortering og innsettingssortering?
Selv om både boblesorterings- og innsettingssorteringsalgoritmene har gjennomsnittlig sakstidskompleksitet O(n2), blir boblesortering nesten hele tiden bedre enn innsettingssorteringen. 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. Det er også en variant av innsettingssortering k alt skallsortering, som har en tidskompleksitet på O(n3/2), som gjør at den kan brukes praktisk t alt. Videre er innsettingssortering svært effektiv for sortering av «nesten sorterte» lister sammenlignet med boblesorteringen.
