Î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.

O primă 'soluţie':job_detail/370055?action=view-source, care numără pentru fiecare element câte elemente sunt mai mici decât el, având complexitatea de <tex>O(N^2)</tex>, şi ar trebui să obţină $20$ puncte.

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

*Marius* Mai e o soluţie în O(N*K), care rulează selection sort de K ori. Dacă ai K mic atunci ia multe puncte. Poate bagi o sursă.

O altă 'soluţie':job_detail/371158?action=view-source care selectează cele mai mici $K$ elemente, având complexitatea $O(N*K)$ obţine în jur de $20$ puncte.

Altă 'soluţie':job_detail/369661?action=view-source care sortează elementele în ordine crescătoare şi are complexitatea <tex>O(Nlog_{2}N)</tex> ar trebui să obţină $50$ puncte.

*Marius* Un radix sort cât să ia? Grupezi câte 2^16. Are *O(N)*.
*Mishu* O(N+K)? Nu iese O(N)? adica sortez şirul si afişez elementul $K$. *Marius* Ba da, să îi zicem O(N) cu radix sort.

O altă 'soluţie':job_detail/369662?action=view-source, cu complexitatea <tex>O(Nlog_{2}K)</tex>, care foloseşte un heap pentru a menţine cele mai mici $K$ elemente ar trebui să obţină $60$ puncte.

O altă 'soluţie':job_detail/369662?action=view-source, cu complexitatea <tex>O(Nlog_{2}K)</tex>, care foloseşte un heap pentru a menţine cele mai mici $K$ elemente ar trebui să obţină $70$ puncte.

O 'soluţie':job_detail/371166 care sortează elementele în timp aproape liniar, folosind radix sort ar trebui să obţină în jur de $70$ de puncte.

*Marius* Se poate mai bine de O(N logK). Poţi crea un min-heap în O(N) din care extragi K elemente. Deci O(N + KlogK) cât să ia?
*Mishu* Nu am înţeles exact această soluţie, cum creez un heap în O(N) şi cum extrag K elemente în O(KlogK), nu ar trebui să fie O(KlogN)?
*Marius* Găseşti aici http://en.wikipedia.org/wiki/Selection_algorithm la „Data structure based solutions”. Un heap îl construieşti în O(N) dintr-un şir de numere (găseşti în CLR). Pe acest min-heap realizezi un BF din rădăcină, dar în loc să reţii un queue reţii o coadă cu priorităţi ce îţi spune cele mai mici cel mult K elemente. Când ai parcurs K elemente te opreşti, iar nodul din vârful cozii de priorităţi e rezultatul. Lucru posibil deoarece min-heap[părinte(i)] >= min-heap[i].
 
Î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>, î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.

Î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>, î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. Există şi o soluţie care garantează $O(N)$ pe cel mai defavorabil caz, care se poate găsi în Cormen la capitolul "Statistici de Ordine".

*Marius* Ideal ar fi ca O(N^2^) *10*, O(N*K) *20*, O(N logN) 40, O(N logK) 50, O(N+KlogK) 60, *O(N) cu radix sort* 70, O(N) 100. Am vorbit cu Paul şi am ajuns la concluzia că implementat de mână ca în Cormen avem worst case O(N^2), însă cu STL worst case e O(N logN) deoarece... aici mă mai gândesc, dar tind să cred că se bazează pe introsortul lui QuickSort. Algoritm O(N) de selecţie este cel cu împărţire în bucăţi de câte 5 elemente, însă, în practică, se comportă mai prost decât cel care alege un pivot aleator. Eu zic să bagi o sursă care nu alege un pivot aleator (ci pe primul) pentru comparaţie cu cea care alege pivotul aleator şi să zici decât că există acest algoritm teoretic cu cu ordinul de execuţie O(N) (şi nu O(N) în medie). Nu mă gândeam că ies atâtea surse. :)