Jämförelser
Byten
Varv

  • Jämförda
  • Minsta hittills
  • Bytta
  • På plats

Mer om urvalssortering

Urvalssortering

Urvalssortering bygger upp den sorterade listan framifrån. Varje varv går igenom de värden som ännu inte är sorterade, håller reda på det minsta och byter in det på den första osorterade platsen. Spela upp sorteringen i valfri hastighet, eller gå igenom den en jämförelse i taget, och följ räknarna för jämförelser, byten och varv. Tryck på Spela för att se sorteringen, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa vart som helst. Rutorna räknar jämförelser, byten och varv. Välj hur många staplar, hur de börjar, eller skriv dina egna tal. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Välj antal staplar och startordning: slumpad, nästan sorterad, omvänd eller med få unika värden. Eller skriv dina egna tal.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa var som helst i sorteringen.
  3. Se hur det minsta värdet hittills ändras medan sökningen pågår, och bytet som sätter det på plats i slutet av varje varv.

Så fungerar urvalssortering

Titta på varje värde i listan och kom ihåg det minsta. Byt det med det första värdet: den första platsen är nu slutgiltig. Gör sedan samma sak med resten av listan, en plats längre fram. Efter n − 1 varv står varje värde på plats, och det sista hamnar på plats av sig självt.

Många jämförelser, få byten

Sökningen slutar aldrig i förtid, eftersom den bara kan vara säker på vilket värde som är minst när den har tittat på alla återstående. Därför gör urvalssortering exakt n(n − 1)/2 jämförelser för n värden, oavsett om listan är sorterad, omvänd eller slumpad. I gengäld gör den högst n − 1 byten, ett per varv. Det gör den till ett rimligt val när det kostar mycket mer att flytta ett värde än att jämföra två.

Ofta ställda frågor

Hur fungerar urvalssortering?

Den väljer gång på gång ut det minsta värdet som ännu inte är sorterat och byter in det på den första osorterade platsen. Efter varv k innehåller de första k platserna de k minsta värdena i ordning.

Hur många jämförelser och byten gör urvalssortering?

Alltid n(n − 1)/2 jämförelser för n värden: 45 för 10 värden, 780 för 40. Antalet byten är högst n − 1, ett per varv, och färre när det minsta värdet redan står på plats.

Varför tar en sorterad lista lika lång tid som en omvänd?

Eftersom varje varv måste titta på alla återstående värden för att vara säker på att det har hittat det minsta. Till skillnad från bubbelsortering och insättningssortering kan urvalssortering inte se på sina jämförelser att listan redan är sorterad.

Är urvalssortering stabil?

Inte i den vanliga formen. Ett byte kan föra ett värde förbi ett lika stort värde: i 2, 2, 1 byter den första 2:an plats med 1:an och hamnar bakom den andra 2:an. En version som skjuter värden i stället för att byta dem är stabil, men kräver fler förflyttningar.

Skickas mina tal någonstans?

Nej. Sorteringen körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Gå till Editor