Urvalssortering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 februari 2019; kontroller kräver 33 redigeringar .
Urvalssortering
ändamål Sorteringsalgoritm
Datastruktur array
värsta tiden O( n 2 )
Lämpligast tid O( n 2 )
Snittid O( n 2 )
Minneskostnad O(1)
 Mediafiler på Wikimedia Commons

Urvalssortering är en sorteringsalgoritm . _ Det kan vara antingen stabilt eller instabilt. På en matris med n element, har en körtid i värsta fall, medelvärde och bästa fall på Θ ( n 2 ), förutsatt att jämförelser görs i konstant tid.

Algoritm utan extra minnesallokering

Algoritmsteg:

  1. hitta numret på minimivärdet i den aktuella listan
  2. vi byter ut detta värde med värdet av den första osorterade positionen (utbytet behövs inte om minimielementet redan är på denna position)
  3. nu sorterar vi baksidan av listan, exkluderar redan sorterade element från övervägande

Ett exempel på en instabil implementering:

C++

mall < typnamn typ_arr > void selection_sort ( typ_arr * arr , int size ) { för ( int i = 0 ; i < storlek - 1 ; i ++ ) { int min_index = i ; för ( int j = i + 1 ; j < storlek ; j ++ ) { if ( arr [ j ] < arr [ min_index ]) { min_index = j ; } } if ( min_index != i ) { swap ( arr [ i ], arr [ min_index ]); } } }

C#

offentlig statisk IList < T > Urval < T > ( IList < T > lista ) där T : IComparable < T > { för ( int i = 0 ; i < lista . Räkna - 1 ; ++ i ) { int min = i ; för ( int j = i + 1 ; j < lista . Räkna ; ++ j ) { if ( lista [ j ]. CompareTo ( lista [ min ]) < 0 ) { min = j ; } } vardummy = lista [ i ] ; lista [ i ] = lista [ min ]; lista [ min ] = dummy ; } returlista ; _ }

PL/SQL

typ sort_choice_list är en tabell över heltalsindex med binärt_heltal ; -------------------------------------------------- -- funktion SORT_CHOICE returnerar sort_vallista ÄR list sort_choise_list ; l_min pls_integer ; l_dummy pls_integer ; Börja för n i 1 .. 100 slingor lista ( n ): = dbms_random . slumpmässigt ; --arrayinitiering med slumptal end -loop ; för jag i listan . första .. lista . sista slingan l_min : = i ; för j in ( i + 1 ) .. lista . sista slingan om ( lista ( j ) < lista ( l_min )) då l_min : = j ; sluta om ; end -loop ; l_dummy : = lista ( i ); lista ( i ): = lista ( l_min ); lista ( l_min ) : = l_dummy ; end -loop ; returlista ; _ slut SORT_CHOICE ;

Java

offentlig statisk < T sträcker sig Jämförbar <? super T >> void sort ( T [] array ) { for ( int i = 0 ; i < array . längd - 1 ; ++ i ) { int minPos = i ; for ( int j = i + 1 ; j < array . längd ; ++ j ) { if ( array [ j ] . compareTo ( array [ minPos ] ) < 0 ) { minPos = j ; } } T saveValue = array [ minPos ] ; array [ minPos ] = array [ i ] ; array [ i ] = saveValue ; } }

rubin

def selection_sort ( array ) för min i 0 .. array . räkna - 2 minst = min för j in ( min + 1 ) .. array . räkna - 1 om array [ j ] < array [ minst ] minst = j slutet slutet temp = array [ min ] array [ min ] = array [ minst ] array [ minst ] = temp slutet slutet

Snabb

func selectionSort < Element >( _ array : inout Array < Element >) där Element : Comparable { för min i 0. .< array . räkna - 1 { för j i min ..< array . räkna { if array [ j ] < array [ min ] { låt temp = array [ min ] array [ min ] = array [ j ] array [ j ] = temp } } } }

PascalABC.NET

Börja var a := ArrRandom ; a . Println ; för var i := 0 till a . Hög göra Swap ( a [ i ] , a [ i + a [ i : ] . IndexMin ]) ; a . Println ; slutet

Pytonorm

def select_sort ( A ): för i inom intervallet ( len ( A ) - 1 ): för k i intervallet ( i + 1 , len ( A )): om A [ k ] < A [ i ]: A [ k ], A [ i ] = A [ i ], A [ k ]

gå

func selectionSort ( nums [] int ) { n := len ( nums ) för i := 0 ; i < n ; i ++ { min := i för j := i + 1 ; j < n ; j ++ { if nums [ j ] < nums [ min ] { min = j } } nums [ i ], nums [ min ] = nums [ min ], nums [ i ] } }

Låt oss visa varför denna implementering är instabil.
Tänk på följande array av element, vart och ett med två fält. Sortering sker på det första fältet.
Array före sortering:
{ (2, a), (2, b), (1, a) }
Redan efter den första iterationen av den yttre slingan kommer vi att ha en sorterad sekvens:
{ (1, a), (2, b), (2, a) }
Notera nu att den relativa positionen för elementen (2, a) och (2, b) har ändrats. Den övervägda implementeringen är således instabil.


Eftersom endast ett utbyte görs efter varje passage genom den inre slingan är det totala antalet utbyten N-1, vilket är N/2 gånger mindre än i bubbelsortering .
Antalet passeringar genom den inre slingan är N-1 även om man sorterar en delvis eller helt sorterad array.

Värsta fallet:
Antalet jämförelser i slingkroppen är (N-1)*N/2.
Antal jämförelser i loophuvuden (N-1)*N/2.
Antal jämförelser före utbytesoperation N-1.
Det totala antalet jämförelser är N 2 −1.
Antal byten N-1.

Bästa fall:


Tiden för sortering av 10 000 korta heltal på samma maskin- och mjukvarusystem efter urvalssort var ≈40 sek, och ännu mer förbättrad bubbelsortering var ≈30 sek.

Heapsort förbättrar avsevärt den underliggande algoritmen genom att använda en heapdatastruktur för att påskynda hitta och ta bort minimielementet.

Det finns också en dubbelriktad variant av urvalssort, där både lägsta och högsta värden hittas och sätts på plats vid varje pass.

Litteratur

  • Levitin A. V. Kapitel 3. Brute force method: Selection sort // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 143-144. — 576 sid. — ISBN 978-5-8459-0987-9
  • Robert Sedgwick. Del III. Kapitel 6. Elementära sorteringsmetoder: 6.2 Urvalssortering // Algoritmer i C++ = Algoritmer i C++. - M . : "Williams" , 2011. - S. 246-247. - ISBN 978-5-8459-1650-1 .
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 .

Se även

Länkar

 Sorteringsalgoritmer
Teori Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta
Val
Insatser
fusion
Inga jämförelser
hybrid
Övrig
opraktisk