Urvalssortering
Urvalssortering sorterar en lista som många sorterar korten på handen: hitta det minsta, lägg det först, och hitta sedan det minsta av resten. Den gör många jämförelser men väldigt få byten, och körtiden beror knappt på listans ordning.
Idén
Dela listan i en sorterad del till vänster, tom från början, och en osorterad del till höger. Gå igenom den osorterade delen och kom ihåg var dess minsta värde står. Byt det värdet med det första osorterade värdet: den sorterade delen har vuxit med ett. Upprepa tills bara ett värde är kvar, och det måste vara det största.
Ett exempel
Ta 5, 1, 4, 2, 8. Första varvet tittar på alla fem värden, hittar 1 som minst och byter det med 5: 1, 5, 4, 2, 8. Andra varvet tittar på 5, 4, 2, 8, hittar 2 och byter det med 5: 1, 2, 4, 5, 8. Tredje varvet hittar 4 redan på plats, och fjärde hittar 5 redan på plats, så inget flyttas. Det blir 4 + 3 + 2 + 1 = 10 jämförelser och bara 2 byten. Bubbelsortering behöver 4 byten för samma lista.
Alltid lika många jämförelser
För att vara säker på vilket värde som är minst måste sökningen titta på varje värde som är kvar. Varv 1 gör n − 1 jämförelser, varv 2 gör n − 2, och så vidare ner till 1, vilket blir n(n − 1)/2 totalt. Talet beror inte på listan: en sorterad lista kostar exakt lika många jämförelser som en omvänd. Urvalssortering kan inte sluta i förtid, eftersom en sökning som hittar det minsta värdet redan först inte har lärt sig något om resten.
Få byten
Varje varv gör högst ett byte, så urvalssortering gör aldrig fler än n − 1 byten, och hoppar över bytet när det minsta värdet redan står på plats. Bubbelsortering och insättningssortering gör lika många byten som det finns par i fel ordning, vilket kan vara ungefär n²/2. När det är mycket dyrare att skriva ett värde än att läsa två, till exempel i minne som slits vid varje skrivning, är det låga antalet byten en fördel.
Inte stabil
En sortering är stabil när lika värden behåller sin ursprungliga ordning. Urvalssortering är det inte, eftersom ett byte över långt avstånd kan föra ett värde förbi ett lika stort. I 2, 2, 1 byter första varvet den första 2:an med 1:an, vilket ger 1, 2, 2 med de två 2:orna nu i omvänd ordning. En version som skjuter värdena emellan i stället för att byta är stabil, men flyttar betydligt fler värden.
Utforska den
Öppna appen och tryck på Spela, eller tryck på Steg för att gå en jämförelse i taget. Värdet som granskas är markerat, det minsta värdet hittills har en egen färg, och varje varv slutar med ett byte in i den sorterade delen till vänster. Prova en sorterad och en omvänd lista: jämförelserna blir lika många, bara bytena skiljer sig.
Ofta ställda frågor
Vilken tidskomplexitet har urvalssortering?
O(n²) i alla fall: exakt n(n − 1)/2 jämförelser för n värden, oavsett ordning. Den gör högst n − 1 byten och behöver bara O(1) extra minne.
Vad är skillnaden mellan urvalssortering och bubbelsortering?
Bubbelsortering byter grannar under tiden och kan sluta i förtid när ett varv inte gör några byten. Urvalssortering kommer bara ihåg var det minsta värdet står och gör ett byte i slutet av varje varv. Urvalssortering gör färre byten; bubbelsortering är snabbare på listor som är nästan sorterade.
Är urvalssortering stabil?
Nej. Ett byte kan flytta ett värde förbi ett annat, lika stort värde, så lika värden kan byta ordning. Den kan göras stabil genom att skjuta värden i stället för att byta dem, vilket kostar fler förflyttningar.
Hur hänger heapsort ihop med urvalssortering?
Heapsort är en urvalssortering med ett snabbare sätt att hitta nästa värde: den håller den osorterade delen i en heap, så varje urval tar ungefär log n steg i stället för en hel genomsökning. Det sänker totalen till O(n log n).
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova urvalssortering