Urvalssortering
Hittar det minsta kvarvarande värdet och byter in det på nästa plats. Den gör väldigt få byten, men alltid lika många jämförelser.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- nej
- ja
Bästa fall: hur tiden växer med listans storlek n när indata är den lättaste för den här algoritmen.
Genomsnitt: hur tiden brukar växa med n. Med n² tar dubbla antalet värden ungefär fyra gånger så lång tid. n log n växer mycket långsammare.
Värsta fall: tillväxten på den svåraste indatan. Viktigt när hastigheten aldrig får sjunka.
Minne: hur mycket extra minne som behövs utöver listan. 1 betyder några variabler, n betyder en kopia av listan.
Stabil: två lika värden behåller sin ursprungliga ordning. Viktigt när man sorterar poster efter ett fält.
Utan extra minne: sorterar inuti själva listan, utan en andra lista.
- jämförs
- flyttas
- minsta hittills
- på slutgiltig plats
Prova det här: Välj en omvänd lista. Antalet jämförelser blir exakt detsamma som för vilken annan lista som helst.
Så fungerar det
Leta igenom den osorterade delen och hitta det minsta värdet. Byt plats på det och det första osorterade värdet, så hamnar ett värde till på sin slutgiltiga plats. Den kontrollerar alltid alla kvarvarande värden, även när listan redan är sorterad.
När det är ett bra val
Användbar när det är dyrt att flytta data men billigt att läsa den. Den byter nämligen högst en gång per plats. I de flesta andra fall är insättningssortering det bättre enkla valet.