Bedste svar
Først og fremmest skal man spørge, hvorfor bruge en kvadratisk sorteringsalgoritme, når der findes asymptotisk hurtigere alternativer, som fusionsort eller quicksort. For små arrays (mindre end 20-30 elementer) er både indsætningssortering og valgsortering hurtigere end O (n * logn) -alternativerne. Faktisk skifter mange sorteringsalgoritmer baseret på delings- og erobringsparadigmet til indsættelsessortering eller markeringssortering, når arrayet er lille nok.
Mellem indsættelsessortering og valgsort, hvornår skal man bruge hvilken?
Normalt udfører indsættelsessortering færre sammenligninger end valgsortering, afhængigt af graden af ”sortering” af arrayet. Mens valgsortering skal scanne de resterende dele af arrayet, når et element placeres, scannes indsættelsessortering kun så mange elementer som nødvendigt. Det betyder, at når arrayet allerede er sorteret eller næsten sorteret, udføres indsættelsessortering på O (n) tid.
En fordel ved valgsortering i forhold til indsættelsessortering er, at antallet af skrivninger (swaps) er i O (n), mens det under indsætning er i O (n ^ 2). Dette kan være vigtigt, hvis du f.eks. Sorterer på Flash-hukommelse, fordi skrivning reducerer Flash-hukommelsens levetid.
Svar
I en valgsortering for hvert element, der skal tilføjes til det sorterede afsnit, skal du scanne hele usorterede del af listen for at finde det mindste resterende element. I en indsættelsessortering skal du søge i sektionen sorteret for at finde ud af, hvor det næste element går, men søgningen slutter, når du har fundet indsættelsespunktet (ca. halvdelen vej gennem det sorterede afsnit i gennemsnit).
Så valgsortering kræver N / 2-sammenligninger i gennemsnit for hvert element, der skal føjes til den sorterede sektion, og indsættelsessorteringen kræver N / 4-sammenligninger i gennemsnit. Indsættelsessortering har dog en yderligere tidsstraf, når man sorterer en matrix. Hver af N / 4 (i gennemsnit) sammenligninger kræver, at elementet forskydes, så der er også N / 4 bevægelser såvel som sammenligninger. Valgssortering kræver kun en enkelt swap.
Generelt vinder indsættelsessorter normalt løbet. Dette gælder især, hvis der er hurtige “block move” -funktioner rundt (for arrays).