[C] Ricerca del k-mo elemento minimo di un array

[militandri]

Secondo me ti conviene semplicemente ordinare tutto l'array e poi scorrerlo per trovare il k-esimo minimo.

[Scara95]

Secondo me ti conviene semplicemente ordinare tutto l'array e poi scorrerlo per trovare il k-esimo minimo.

Aveva specificato "usando il partizionamento" nel testo.

In ogni caso un ordinamento supponendo un qsort ha complessità O(n*log(n)) nel caso medio O(n*n) nel caso pessimo
L'algoritmo di cui sopra ha complessità O(log(n)) nel caso medio O(n*n) nel caso pessimo

E oltretutto, se si vuole un tempo di risposta più prevedibile con un caso pessimo migliore è più opportuno usare una min-heap e k pop: O(n+k*log(n)) che rimane comunque migliore dell'ordinamento.

Ma tutto ciò è inutile, viste le premesse: "usando il partizionamento".

Edit: dimenticavo, una volta ordinato l'array non ti servirebbe nemmeno scorrerlo...