În exemplu, se observă că elementele aranjate în ordine crescătoare sunt: $1 4 **6** 7 10 11 13 14$, prin urmare al $3$-lea cel mai mic element este $6$.

h2. Soluţie

h2. Indicaţii de rezolvare

'Soluţia':job_detail/370055?action=view-source ce numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de <tex> O(n^2) </tex>, ar trebui să obţină $10$ puncte.

'Soluţia':/job_detail/372622?action=view-source cea mai eficientă foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a $k$-a statistică de ordine. Practic, acest algoritm este asemănător algoritmului 'Quicksort':http://en.wikipedia.org/wiki/Quicksort, cu deosebirea că se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. Însă, această soluţie obţine $90$ de puncte. În 'sursa':job_detail/372623?action=view-source de $100$ de puncte se va folosi un pivot ales aleator, în locul unui pivot fixat. Complexitatea acestui algoritm este în medie <tex> O(n) </tex>, însă, teoretic, în cel mai defavorabil caz poate atinge <tex> O(n^2) </tex> pentru că am putea fi extrem de nenorocoşi să partiţionăm în jurul celui mai mare element rămas. Dar, deoarece algoritmul este aleator, nu există date de intrare particulare care să provoace comportamentul celui mai defavorabil caz. Iată motivul pentru care algoritmul ce selectează pivotul random este mai eficient decât cel care selectează un pivot fixat. Acest algoritm este implementat şi în STL: funcţia 'nth_element':http://cplusplus.com/reference/algorithm/nth_element/ găsindu-se în headerul 'algorithm':http://cplusplus.com/reference/algorithm/. O sursă demonstrativă se găseşte 'aici':job_detail/369659?action=view-source. Există şi un algoritm teoretic ce garantează <tex> O(n) </tex> pe cel mai defavorabil caz, şi se poate găsi în cartea '„Introducere în algoritmi”':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm la capitolul '„10. Statistici de Ordine”':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap10.htm.

h3. Aplicaţii

h2. Aplicaţii

* 'Toys':problema/toys
* 'Geometrie':problema/geom