Forskjellen mellom boble sortering og innsettings sortering
Share
Boble sortering vs Insertion Sorter
Boble sortering er en sorteringsalgoritme som opererer ved å gå gjennom listen som skal sorteres 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 tverrsnittet gjentas til det ikke kreves ytterligere bytteer. Innsats sortering er også en sorteringsalgoritme, som opererer ved å sette inn et element i inntastingslisten inn i riktig posisjon i en liste som allerede er sortert. Denne prosessen brukes gjentatte ganger til listen er sortert.
Hva er Bubble Sort?
Boble sortering er en sorteringsalgoritme som opererer ved å gå gjennom listen som skal sorteres 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 tverrsnittet gjentas til det ikke kreves ytterligere bytteavtaler (hvilket betyr at listen er sortert). Siden de minste elementene i listen kommer til toppen når en boble kommer til overflaten, er det gitt navnet boble sortering. Bubblesort er en veldig enkel sorteringsalgoritme, men den har en gjennomsnittlig sakkompleksitet på O (n2) når du sorterer en liste med n elementer. På grunn av dette er boble sorter ikke egnet for sortering av lister med et stort antall elementer. Men på grunn av sin enkelhet læres boblesorte under introduksjoner til algoritmer.
Hva er Insertion Sorter?
Innsats sortering er en annen sorteringsalgoritme, som opererer ved å sette inn et element i inntastingslisten inn i riktig posisjon i en liste (som allerede er sortert). Denne prosessen brukes gjentatte ganger til listen er sortert. I innførings sortering utføres sorteringen på plass. Derfor blir det første i + 1-oppføringene i listen sortert etter algoritmen, og resten av listen blir usortert. Ved hver iterasjon blir det første elementet i den usorterte delen av listen tatt og satt inn på riktig sted i den sorterte delen av listen. Innsats sortering har en gjennomsnittlig tilfelle tid kompleksitet av O (n2). På grunn av dette er ikke innføringssort egnet for sortering av store lister.
Hva er forskjellen mellom sortering og sortering av bobler?
Selv om både boble sortering og innføring sorteringsalgoritmer har gjennomsnittlig tilfelle tidskompleksiteter av O (n2), er boble sorter nesten hele tiden bedre enn innsats sorteringen. Dette skyldes antall swaps som trengs av de to algoritmene (boble sorter trenger flere swaps). Men på grunn av enkelhet av boble sorter, er koden størrelse veldig liten. Også det er en variant av innsettingstype som heter shell-sorten, som har en tidskompleksitet på O (n3 / 2), som vil tillate det å brukes praktisk. Videre er innførings sorter veldig effektiv for sortering av "nesten sorterte" lister, sammenlignet med boblesorten.
