Skillnad mellan sortering av bubbla och infogning

Bubbla Sort vs Insertion Sortera

Bubbelsort är en sorteringsalgoritm som fungerar genom att gå igenom listan som ska sorteras upprepade gånger medan man jämför parpar av element som ligger intill. Om ett par element är i fel ordning bytas de för att placera dem i rätt ordning. Denna traverse upprepas tills inga ytterligare swappar krävs. Infognings sortering är också en sorteringsalgoritm som fungerar genom att infoga ett element i inmatningslistan till rätt position i en lista som redan är sorterad. Denna process tillämpas flera gånger tills listan är sorterad.

Vad är bubbelsort?

Bubbelsort är en sorteringsalgoritm som fungerar genom att gå igenom listan som ska sorteras upprepade gånger medan man jämför parpar av element som ligger intill. Om ett par element är i fel ordning bytas de för att placera dem i rätt ordning. Denna traverse upprepas tills inga ytterligare swappar krävs (vilket innebär att listan sorteras). Eftersom de mindre elementen i listan kommer till toppen när en bubbla kommer till ytan, ges den namnet bubbelsort. Bubbelsort är en mycket enkel sorteringsalgoritm men den har en genomsnittlig fallkomplexitet på O (n2) när du sorterar en lista med n-element. På grund av detta är bubbelsort inte lämpligt för sortering av listor med ett stort antal element. Men på grund av sin enkelhet lärs bubbelsort under introduktioner till algoritmer.

Vad är Insertion Sortera?

Infognings sortering är en annan sorteringsalgoritm, som fungerar genom att infoga ett element i ingångslistan till rätt position i en lista (som redan är sorterad). Denna process tillämpas flera gånger tills listan är sorterad. I sortsortering utförs sortering på plats. Därför sorteras de första i + 1-posterna i listan efter resten av listan och resten av listan blir osorterad. Vid varje iteration tas det första elementet i den osorterade delen av listan och läggs in på rätt plats i den sorterade delen av listan. Infogningssort har en genomsnittlig fallkomplexitet på O (n2). På grund av detta är inte inmatningssort lämpligt för sortering av stora listor.

Vad är skillnaden mellan Bubbelsort och Insertion Sortera?

Även om både sorteringsalgoritmerna för bubbla sorterar och införs har genomsnittliga fallkomplexiteter av O (n2), är bubbelsorten nästan hela tiden överträffad av införingssorten. Detta beror på antalet swappar som behövs av de två algoritmerna (bubbelsorter behöver fler swappar). Men på grund av enkelhetens bubbelsort är kodens storlek mycket liten. Också det finns en variant av insättningssort som heter shell-sorten, som har en tidskomplexitet på O (n3 / 2), vilket skulle göra det möjligt att använda det praktiskt. Vidare är inmatningssort mycket effektivt för sortering av "nästan sorterade" listor, jämfört med bubbelsorten.