Udvælgelsessortering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. februar 2019; checks kræver 33 redigeringer .
Udvælgelsessortering
formål Sorteringsalgoritme
Datastruktur array
værste tid O( n 2 )
Bedste tid O( n 2 )
Gennemsnitlig tid O( n 2 )
Hukommelsesomkostninger O(1)
 Mediefiler på Wikimedia Commons

Udvælgelsessortering er en sorteringsalgoritme . _ Det kan enten være stabilt eller ustabilt. På et array af n elementer, har en worst-case, gennemsnit og best-case runtime på Θ ( n 2 ), forudsat at sammenligninger foretages i konstant tid.

Algoritme uden yderligere hukommelsesallokering

Algoritme trin:

  1. find nummeret på minimumsværdien i den aktuelle liste
  2. vi udveksler denne værdi med værdien af ​​den første usorterede position (udvekslingen er ikke nødvendig, hvis minimumselementet allerede er på denne position)
  3. nu sorterer vi listens hale og udelukker allerede sorterede elementer fra overvejelse

Et eksempel på en ustabil implementering:

C++

skabelon < typenavn type_arr > void selection_sort ( type_arr * arr , int size ) { for ( int i = 0 ; i < størrelse - 1 ; i ++ ) { int min_indeks = i ; for ( int j = i + 1 ; j < størrelse ; j ++ ) { if ( arr [ j ] < arr [ min_index ]) { min_indeks = j ; } } if ( min_indeks != i ) { swap ( arr [ i ], arr [ min_indeks ]); } } }

C#

offentlig statisk IList < T > Udvælgelse < T > ( IList < T > liste ) hvor T : IComparable < T > { for ( int i = 0 ; i < liste . Count - 1 ; ++ i ) { int min = i ; for ( int j = i + 1 ; j < liste . Antal ; ++ j ) { if ( liste [ j ]. Sammenlign Til ( liste [ min ]) < 0 ) { min = j ; } } vardummy = liste [ i ] ; liste [ i ] = liste [ min ]; liste [ min ] = dummy ; } returliste ; _ }

PL/SQL

type sort_choice_list er tabel med heltalsindeks efter binært_heltal ; _ -------------------------------------------------- -- funktion SORT_CHOICE returner sort_valgsliste ER liste sort_valgliste ; l_min pls_integer ; l_dummy pls_integer ; begynde for n i 1 .. 100 sløjfer liste ( n ): = dbms_random . tilfældig ; --array initialisering med tilfældige tal ende -løkke ; for jeg på listen . første .. liste . sidste sløjfe l_min : = i ; for j i ( i + 1 ) .. liste . sidste sløjfe hvis ( liste ( j ) < liste ( l_min )) derefter l_min : = j ; ende hvis ; ende -løkke ; l_dummy : = liste ( i ); liste ( i ): = liste ( l_min ); liste ( l_min ) : = l_dummy ; ende -løkke ; returliste ; _ ende SORT_CHOICE ;

Java

offentlig statisk < T udvider Sammenlignelig <? super T >> void sort ( T [] array ) { for ( int i = 0 ; i < matrix . længde - 1 ; ++ i ) { int minPos = i ; for ( int j = i + 1 ; j < array . længde ; ++ j ) { if ( array [ j ] . compareTo ( array [ minPos ] ) < 0 ) { minPos = j ; } } T saveValue = matrix [ minPos ] ; array [ minPos ] = array [ i ] ; array [ i ] = gemmeVærdi ; } }

rubin

def selection_sort ( array ) for min i 0 .. array . tæller - 2 mindst = min for j in ( min + 1 ) .. array . tæller - 1 hvis array [ j ] < array [ mindst ] mindst = j ende ende temp = matrix [ min ] matrix [ min ] = matrix [ mindst ] array [ mindst ] = temp ende ende

Swift

func selectionSort < Element >( _ array : inout Array < Element >) hvor Element : Comparable { for min i 0. .< array . tæller - 1 { for j i min ..< array . tælle { if array [ j ] < array [ min ] { lad temp = array [ min ] matrix [ min ] = matrix [ j ] array [ j ] = temp } } } }

PascalABC.NET

begynde var a := ArrRandom ; a . Println ; for var i := 0 til a . Høj gør Swap ( a [ i ] , a [ i + a [ i : ] . IndexMin ]) ; a . Println ; ende

Python

def select_sort ( A ): for i inden for rækkevidde ( len ( A ) - 1 ): for k i området ( i + 1 , len ( A )): hvis A [ k ] < A [ i ]: A [ k ], A [ i ] = A [ i ], A [ k ]

gå

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

Lad os vise, hvorfor denne implementering er ustabil.
Overvej følgende array af elementer, hver med to felter. Sortering foregår på det første felt.
Array før sortering:
{ (2, a), (2, b), (1, a) }
Allerede efter den første iteration af den ydre sløjfe vil vi have en sorteret sekvens:
{ (1, a), (2, b), (2, a) }
Bemærk nu, at den relative placering af elementerne (2, a) og (2, b) er ændret. Den overvejede implementering er således ustabil.


Da der kun foretages én udveksling efter hver passage gennem den indre sløjfe, er det samlede antal udvekslinger N-1, hvilket er N/2 gange mindre end i boblesortering .
Antallet af gennemløb gennem den indre sløjfe er N-1, selvom man sorterer et delvist eller fuldstændigt sorteret array.

Worst case:
Antallet af sammenligninger i loop body er (N-1)*N/2.
Antal sammenligninger i loop-headers (N-1)*N/2.
Antal sammenligninger før udvekslingsoperation N-1.
Det samlede antal sammenligninger er N 2 −1.
Antal centraler N-1.

Bedste tilfælde:


Tidspunktet for sortering af 10.000 korte heltal på det samme hardware- og softwaresystem efter udvælgelsessortering var ≈40 sek., og endnu mere forbedret boblesortering var ≈30 sek.

Heapsort forbedrer i høj grad den underliggende algoritme ved at bruge en heap -datastruktur til at fremskynde at finde og fjerne minimumselementet.

Der er også en tovejsvariant af udvælgelsessortering, hvor både minimums- og maksimumværdierne findes og sættes på plads ved hvert gennemløb.

Litteratur

  • Levitin A. V. Kapitel 3. Brute force metode: Udvælgelsessortering // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 143-144. — 576 s. — ISBN 978-5-8459-0987-9
  • Robert Sedgwick. Del III. Kapitel 6. Elementære sorteringsmetoder: 6.2 Udvælgelsessortering // 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 og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Se også

Links

 Sorteringsalgoritmer
Teori Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling
Valg
indsætter
fusion
Ingen sammenligninger
hybrid
Andet
upraktisk