Beste svaret
Først og fremst bør man spørre hvorfor bruke en kvadratisk sorteringsalgoritme når det eksisterer asymptotisk raskere alternativer, som fusionsort eller kviksort. For små matriser (mindre enn 20-30 elementer) er både innsettingssortering og valgsortering raskere enn O (n * logn) -alternativene. Faktisk bytter mange sorteringsalgoritmer basert på delings- og erobringsparadigmet til innsettingssortering eller utvalgssortering når matrisen er liten nok.
Mellom innsettingssortering og utvalgssortering, når skal du bruke hvilken?
Vanligvis vil innsettingssortering utføre mindre sammenligninger enn utvalgssortering, avhengig av graden av «sortering» i matrisen. Mens utvalgssortering må skanne de gjenværende delene av matrisen når du plasserer et element, skanner innsettingssortering bare så mange elementer som nødvendig. Det betyr at når matrisen allerede er sortert eller nesten sortert, utfører innsettingssortering på O (n) -tid.
En fordel med utvalgssortering fremfor innsettingssortering, er at antallet skriver (bytter) er i O (n), mens det i innsetting er i O (n ^ 2). Dette kan være viktig hvis du for eksempel sorterer på Flash-minne fordi skriving reduserer levetiden til Flash-minne.
Svar
I et utvalg, for hvert element som skal legges til i den sorterte delen, må du skanne hele usorterte delen av listen for å finne det minste gjenværende elementet. I en innsettingssortering må du søke i sortert -delen for å finne ut hvor neste element går, men søket avsluttes når du har funnet innsettingspunktet (omtrent halvparten vei gjennom den sorterte seksjonen i gjennomsnitt).
Så valgsortering krever N / 2-sammenligninger i gjennomsnitt for hvert element som skal legges til den sorterte seksjonen, og innsettingssortering krever N / 4-sammenligninger i gjennomsnitt. Innsettingssortering har imidlertid en ekstra tidsstraff når du sorterer en matrise. Hver av N / 4-sammenligningene (i gjennomsnitt) krever at elementet forskyves oppover, så det er også N / 4-trekk så vel som sammenligninger. Valgsortering krever bare en enkelt bytte.
Generelt vinner innsettingssorter vanligvis løpet. Dette gjelder spesielt hvis det er raske «block move» -funksjoner rundt (for arrays).