Bästa svaret
Först och främst bör man fråga varför använda en kvadratisk sorteringsalgoritm när det finns asymptotiskt snabbare alternativ, som fusionsort eller snabbsort. För små matriser (mindre än 20-30 element) är både insättningssortering och urvalsortering typiskt snabbare än O (n * logn) -alternativen. Faktum är att många sorteringsalgoritmer baserade på delnings- och erövringsparadigmet byter till insättningssortering eller urvalssortering när matrisen är tillräckligt liten.
Mellan insättningssortering och urvalsortering, när ska vilken?
Vanligtvis kommer insättningssortering att utföra mindre jämförelser än urvalsortering, beroende på graden av ”sorterad” i matrisen. Medan urvalssortering måste skanna de återstående delarna av matrisen när ett element placeras, skannar insättningssortering bara så många element som behövs. Det betyder att när arrayen redan är sorterad eller nästan sorterad, utförs insättningssortering på O (n) -tid.
En fördel med urvalssortering framför insättningssortering är att antalet skrivningar (swappar) är i O (n), medan i insättningssortering är det i O (n ^ 2). Detta kan vara viktigt om du till exempel sorterar på Flash-minne, eftersom skrivningar minskar livslängden för Flash-minne.
Svar
I en urvalsortering för varje element som ska läggs till i det sorterade avsnittet, måste du skanna hela osorterade delen av listan för att hitta det minsta kvarvarande elementet. I en insättningssortering måste du söka i avsnittet sorterat för att ta reda på var nästa element går men sökningen slutar när du har hittat insättningspunkten (ungefär hälften vägen genom det sorterade avsnittet i genomsnitt).
Så urvalssortering kräver N / 2-jämförelser i genomsnitt för att varje element ska läggas till i det sorterade avsnittet och insättningssortering kräver i genomsnitt N / 4-jämförelser. Insättningssortering har emellertid en ytterligare tidsfrist när man sorterar en matris. Var och en av N / 4-jämförelserna (i genomsnitt) kräver att elementet flyttas upp så att det också finns N / 4-rörelser såväl som jämförelser. Urvalssortering kräver bara ett enda byte.
Sammantaget vinner insättningssortering vanligtvis loppet. Detta gäller särskilt om det finns snabba ”block move” -funktioner runt (för arrays).