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.
Algoritmin vaiheet:
Esimerkki epävakaasta toteutuksesta:
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 ]); } } } 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 ; 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 ; } } 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 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 } } } } alkaa var a := ArrRandom ; a . Println ; var i : = 0 - a . Korkea tehdä Vaihda ( a [ i ] , a [ i + a [ i : ] . IndexMin ]) ; a . Println ; loppu 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 ] 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.
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ä |