Valinnan lajittelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. helmikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 33 muokkausta .
Valinnan lajittelu
tarkoitus Lajittelualgoritmi
Tietorakenne joukko
pahin aika O( n 2 )
Paras aika O( n 2 )
Keskimääräinen aika O( n 2 )
Muistin hinta O(1)
 Mediatiedostot Wikimedia Commonsissa

Valintalajittelu on lajittelualgoritmi . _ _ Se voi olla joko vakaa tai epävakaa. N elementin joukolla on pahimman tapauksen, keskimääräinen ja parhaan tapauksen suoritusaika Θ ( n 2 ), olettaen, että vertailut tehdään vakioajassa.

Algoritmi ilman lisämuistin varausta

Algoritmin vaiheet:

  1. etsi nykyisen luettelon vähimmäisarvon numero
  2. vaihdamme tämän arvon ensimmäisen lajittelemattoman sijainnin arvoon (vaihtoa ei tarvita, jos minimielementti on jo tässä paikassa)
  3. nyt lajittelemme luettelon loppuosan jättäen jo lajiteltuja elementtejä huomioimatta

Esimerkki epävakaasta toteutuksesta:

C++

malli < typename type_arr > void selection_sort ( type_arr * arr , int size ) { for ( int i = 0 ; i < koko - 1 ; i ++ ) { int min_indeksi = i ; for ( int j = i + 1 ; j < koko ; j ++ ) { if ( arr [ j ] < arr [ min_indeksi ]) { min_indeksi = j ; } } if ( min_indeksi != i ) { swap ( arr [ i ], arr [ min_index ]); } } }

C#

julkinen staattinen ILista < T > Valinta < T > ( ILista < T > lista ) jossa T : IVertailu < T > { for ( int i = 0 ; i < lista . Count - 1 ; ++ i ) { int min = i ; for ( int j = i + 1 ; j < lista . Count ; ++ j ) { jos ( lista [ j ]. Vertaa ( luettelo [ min ]) < 0 ) { min = j ; } } vardummy = lista [ i ] ; lista [ i ] = lista [ min ]; lista [ min ] = dummy ; } palautuslista ; _ }

PL/SQL

type sort_choice_list on taulukko kokonaislukuindeksistä binäärilukujen mukaan ; _ _ --------------------------------------------------- -- funktio SORT_CHOICE palauttaa sort_choice_list ON lista sort_choise_list ; l_min pls_integer ; l_dummy pls_integer ; alkaa n : lle 1 .. 100 silmukkaa lista ( n ): = dbms_random . satunnainen ; --taulukon alustus satunnaisluvuilla end - silmukka ; minulle listassa . _ _ ensimmäinen .. lista . viimeinen silmukka l_min : = i ; j : lle in ( i + 1 ).. lista . viimeinen silmukka if ( lista ( j ) < lista ( l_min )) then l_min : = j ; loppu jos ; end - silmukka ; l_dummy : = lista ( i ); lista ( i ): = lista ( l_min ); lista ( l_min ) : = l_dummy ; end - silmukka ; palautuslista ; _ loppu SORT_CHOICE ;

Java

julkinen staattinen < T ulottuu Vertailukelpoinen <? super T >> void sort ( T [ ] array ) { for ( int i = 0 ; i < taulukko . pituus - 1 ; ++ i ) { int minPos = i ; for ( int j = i + 1 ; j < taulukon pituus ; ++ j ) { _ if ( matriisi [ j ] . vertaaTo ( matriisi [ minPos ] ) < 0 ) { minPos = j ; } } T saveValue = array [ minPos ] ; taulukko [ minPos ] = array [ i ] ; array [ i ] = saveValue ; } }

rubiini

def selection_sort ( matriisi ) min 0 .. taulukossa . _ _ laskea - 2 vähintään = min j in ( min + 1 ) .. taulukko . _ laskea - 1 jos matriisi [ j ] < taulukko [ vähin ] vähintään = j loppu loppu temp = array [ min ] jono [ min ] = jono [ vähin ] array [ vähin ] = temp loppu loppu

Swift

func selectionSort < Element >( _ array : inout Array < Element >) missä Elementti : Vertaileva { min 0. . < taulukossa . _ count - 1 { j :lle min .. < array . count { if array [ j ] < array [ min ] { anna temp = array [ min ] taulukko [ min ] = taulukko [ j ] array [ j ] = temp } } } }

PascalABC.NET

alkaa var a := ArrRandom ; a . Println ; var i : = 0 - a . Korkea tehdä Vaihda ( a [ i ] , a [ i + a [ i : ] . IndexMin ]) ; a . Println ; loppu

Python

def select_sort ( A ): i :lle alueella ( len ( A ) - 1 ) : k :lle alueella ( i + 1 , len ( A ) ): jos A [ k ] < A [ i ]: A [ k ], A [ i ] = A [ i ], A [ k ]

mennä

func selectionSort ( numerot [ ] int ) { n := len ( numerot ) i : = 0 ; i < n ; minä ++ { min := i j : lle := i + 1 ; j < n ; j ++ { jos numerot [ j ] < numerot [ min ] { min = j } } numerot [ i ], numerot [ min ] = numerot [ min ], numerot [ i ] } }

Osoitetaan, miksi tämä toteutus on epävakaa.
Tarkastellaan seuraavaa elementtijoukkoa, joissa jokaisessa on kaksi kenttää. Lajittelu tapahtuu ensimmäisellä kentällä.
Taulukko ennen lajittelua:
{ (2, a), (2, b), (1, a) }
Jo ulomman silmukan ensimmäisen iteraation jälkeen meillä on lajiteltu sekvenssi:
{ (1, a), (2, b), (2, a) }
Huomaa nyt, että elementtien (2, a) ja (2, b) suhteellinen sijainti on muuttunut. Näin ollen tarkasteltu toteutus on epävakaa.


Koska jokaisen sisäisen silmukan läpikulun jälkeen tehdään vain yksi vaihto, vaihtojen kokonaismäärä on N-1, mikä on N/2 kertaa vähemmän kuin kuplalajittelussa .
Sisäsilmukan läpivientien määrä on N-1, vaikka lajitettaisiin osittain tai kokonaan lajiteltu taulukko.

Huonoin tapaus:
Vertailujen määrä silmukan rungossa on (N-1)*N/2.
Vertailujen määrä silmukkaotsikoissa (N-1)*N/2.
Vertailujen lukumäärä ennen vaihtooperaatiota N-1.
Vertailujen kokonaismäärä on N 2 −1.
Vaihtojen määrä N-1.

Paras tapaus:


10 000 lyhyen kokonaisluvun lajitteluaika samassa laitteisto- ja ohjelmistojärjestelmässä valintalajittelun mukaan oli ≈40 sekuntia ja vielä paranneltu kuplalajittelu oli ≈30 sekuntia.

Heapsort parantaa huomattavasti taustalla olevaa algoritmia käyttämällä keon tietorakennetta nopeuttamaan minimielementin löytämistä ja poistamista.

Valintalajittelusta on myös kaksisuuntainen variantti, jossa sekä minimi- että maksimiarvot löydetään ja asetetaan paikoilleen jokaisella kierrolla.

Kirjallisuus

  • Levitin A. V. Luku 3. Raaka voima -menetelmä: Selection sort // Algoritmit. Johdatus kehitykseen ja analyysiin - M . : Williams , 2006. - S. 143-144. — 576 s. — ISBN 978-5-8459-0987-9
  • Robert Sedgwick. Osa III. Luku 6. Alkeiset lajittelumenetelmät: 6.2 Valintalajittelu // Algoritmit C++:ssa = Algoritmit C++:ssa. - M . : "Williams" , 2011. - S. 246-247. - ISBN 978-5-8459-1650-1 .
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Katso myös

Linkit

 Lajittelualgoritmit
Teoria Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen
Vaihto
Valinta
insertit
fuusio
Ei vertailuja
hybridi
muu
epäkäytännöllistä