Forskellen mellem boble sortering og indsættelse sortering

Bubble Sort vs Insertion 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. Indsættelsessortering er også en sorteringsalgoritme, der fungerer ved at indsætte et element i inputlisten til den rigtige position på en liste, der allerede er sorteret. Denne proces anvendes gentagne gange, indtil listen er sorteret.

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 indsættelsessortering?

Indsættelsessortering er en anden sorteringsalgoritme, der fungerer ved at indsætte et element i inputlisten til den rigtige position på en liste (der allerede er sorteret). Denne proces anvendes gentagne gange, indtil listen er sorteret. Ved indsættelsessortering udføres sorteringen på stedet. Derfor efter algoritmens ith-iteration sorteres de første i + 1-poster på listen, og resten af ​​listen bliver ikke sorteret. Ved hver iteration vil det første element i den usorterede del af listen blive taget og indsat på det rigtige sted i den sorterede del af listen. Indsættelsessort har en gennemsnitlig sagstidskompleksitet på O (n2). På grund af dette er indsættelsessortering heller ikke egnet til sortering af store lister.

Hvad er forskellen mellem Bubble Sort og Insertion Sort?

Selvom både bobelsorterings- og indsættelsessorteringsalgoritmer har gennemsnitlige sags tidskompleksiteter på O (n2), er bobelsortering næsten hele tiden bedre end indsættelsessorteringen. 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. Der er også en variant af indsættelsessorter kaldet shell-sorteringen, som har en tidskompleksitet på O (n3 / 2), som ville gøre det muligt at bruge det praktisk. Yderligere er indsættelsessortering meget effektiv til at sortere "næsten sorterede" lister sammenlignet med boble sortering.