Valinta-algoritmi

Valinta-algoritmi on algoritmi, jonka tehtävänä on valita tietty alkio joukosta, yleensä jollain erityisellä perusteella, kuten pienin, suurin, mediaani tai muu määritelty arvo. Valinta-algoritmit ovat keskeisiä tietojenkäsittelytieteessä ja niitä käytetään monilla eri alueilla, kuten lajittelussa, optimoinnissa ja tilastotieteessä. Valinta-algoritmeja voidaan käyttää erityisesti silloin, kun halutaan etsiä joukosta vain yksi arvo ilman, että koko joukkoa tarvitsee järjestää.

Yksinkertaisin ja yleisin valinta-algoritmi on lineaarinen valinta, jossa käydään koko joukko läpi ja etsitään pienin tai suurin arvo. Tämä algoritmi on yksinkertainen ja toimii kaikissa tietorakenteissa, joissa alkioihin pääsee käsiksi ja niitä voidaan vertailla. Tyypillisesti sitä käytetään epäjärjestetyissä taulukoissa tai linkitetyissä listoissa.

Jos tietorakenteessa on erityistä rakennetta, valinta-algoritmi voi hyödyntää tätä tietoa. Esimerkiksi binäärihakupuu mahdollistaa tehokkaamman valinnan, jos puu on tasapainoinen, sillä se jakaa joukon jatkuvasti pienempiin osiin. Tällöin voidaan etsiä nopeasti joko pienintä tai suurinta arvoa.

QuickSelect on yksi tehokkaimmista valinta-algoritmeista, joka käyttää jakamista ja valloittamista (divide-and-conquer) -periaatetta. Se valitsee arvon osittain lajittelemalla joukon ja toimii keskimäärin O(n) ajassa, mutta pahimmassa tapauksessa sen aikavaativuus voi olla O(n²).

Medianin valinta on erityinen valinta, jossa etsitään joukon mediaani. Erityisesti Median of Medians -algoritmi tarjoaa tavan löytää mediaani tietyllä aikarajoituksella O(n), mikä takaa sen, että algoritmi ei mene huonompaan suuntaan suurilla syötteillä. Tämä tekee siitä tehokkaan, jos tavoitellaan suuria syötteitä.