În final, 'soluţia':job_detail/369692?action=view-source care ar trebui să obţină $100$ de puncte foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a $K$-a statistică de ordine. Practic, acest algoritm este foarte asemănător quicksort-ului, doar că în loc să se sorteze tot şirul se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. 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. Complexitatea acestui algoritm este în medie <tex>O(N)</tex>, dar în cel mai defavorabil caz poate atinge <tex>O(N^2)</tex>

*Marius* Nu ar fi mai bine ca O(N^2^) 20p, O(N logN) 50p, O(N logK) 60-70, O(N) 100? Când atinge O(N^2^) algoritmul O(N)?
 

h3. Aplicaţii
* 'Toys':problema/toys