Newsgroup: it.comp.java
Titolo: n-esimo maggiore in un vettore

devo trovare l'ennesimo maggiore in un vttore di interi.
La firma del metodo *deve* essere
public staic int findNMax(int[] vettore, int n)
Se voglio trovare il secondo maggiore scrivero
int secondoPiuGrande=NomeClasse.findNMax(vettore,2)
Come devo fare, pensavo ad un metodo di ausilio che mi elimini
dal vettore sempre il piu grande (restituendolo), e iterare tale 
metodo n volte (Se voglio l'nesimo maggiore).
Che mi consgigliate?
grazie

 devo trovare l'ennesimo maggiore in un vettore di interi.
[CUT]
Quello che tu dici non è molto efficiente...infatti nel caso pessimo ha un
tempo di esecuzione O(n^2).
Il problema che hai descritto è il classico problema della *selezione* .
Potrebbe essere più efficiente un algoritmo del genere (in pseudocodice):
quickselect(L,k)
    {
        pick x in L  //sceglie un pivot nell'array
        //partiziona l'array in 3 sub-array:
        partition L into (L1: elem<x), (L2: elem==x), (L3: elem>x) 
 
        //ci saranno lenght(L1) elementi < del pivot
        //se l'elem. cercato è < di lenght(L1), sarà in L1
        if (k <= length(L1))
            return quickselect(L1,k)
        //se è > di lenght(L1)+lenght(L2) sarà in L3
        else if (k > length(L1)+length(L2))
            return quickselect(L3,k-length(L1)-length(L2))
        //altrimenti è in L2, ovvero è proprio il pivot
        else return x
    }
Si dimostra che il numero atteso di confronti nel caso medio è ~4n.
Ciao.
-- 
"It is impossible to teach good programming to students who have had a prior
exposure to BASIC: as potential programmers they are mentally mutilated
beyond hope of regeneration."
(E. W. Dijkstra)

 devo trovare l'ennesimo maggiore in un vttore di interi.
io farei questa cosa semplicissima:
public staic int findNMax(int[] vettore, int n) {
 Arrays.sort(vettore);
 return vettore[vettore.length-n];
}
Aggiungendo magari qualche controllo sull'input. Ho considerato n compreso
tra 1 e vettore.length, è giusto no?
Il costo è ovviamente quello di un ordinamento.
Secondo la documentazione di Java:
This algorithm offers n*log(n) performance on many data sets that cause
other quicksorts to degrade to quadratic performance
Ciao
Matteo
-- 
chi sono e soprattutto chi non sono:
http://www.ilnomedeldominio.it
un piccolo programma per studenti universitari:
http://inutility.ilnomedeldominio.it/imsv/

 
Io userei una specie di bubble sort che invece di girare n^2 volte 
gira solo N volte (con N il tuo parametro) e poi restituisco l'N-esimo 
elemento del vettore. Togliere ogni volta un elemento dal vettore 
puo' dare problemi ad esempio se nel chiamante ti aspetti di nuovo il 
vettore integro.
Ciao

 Ciao
Questo nel caso peggiore (cioè se l'n-esimo è proprio l'ultimo, il più
piccolo per capirci) ha comunque il tempo di esecuzione di bubblesort, cioè
O(n^2). In sostanza è lo stesso algoritmo proposto da Cor_Pie(), ma non
"toglie" elementi all'array.
Più in generale, visto che si tratta di *selezionare* il valore che in caso
di array ordinato sarebbe all'n-esimo posto, ordinare *tutto* l'array
comporta un numero di confronti decisamente alto per il problema in
questione, soprattutto con un algoritmo O(n^2).
Ma l'algoritmo che ho riportato (non è mio, ovviamente) nell'altro post non
vi piace proprio? ;)
Si basa sostanzialmente su quicksort, il tempo di esecuzione nel caso medio
è O(n), e la costante moltiplicativa è decisamente bassa (circa 4). E il
caso medio si presenta praticamente sempre ;) .
Floyd e Rivest hanno proposto qualcosa di più veloce mi pare, ma comunque
O(n).
Ciao :)


non vi piace proprio? ;)
a parte il fatto che non l'ho capito tanto, non è che non mi piaccia :) E'
che se le prestazioni non sono essenziali sfruttando l'api di Java bastano
2 righe. Mentre implementare qull'algoritmo è sicuramente piu' difficile
-soggetto ad errori - meno leggibile. E anche parlando di prestazioni si
tratta della differenza tra O(n) e O(nlogn).
Per fartela breve per quanto mi riguarda è piu' che altro pigrizia :)


 Matteo
In quanto a pigrizia trovi un sicuro alleato ;)
Se le prestazioni non sono essenziali cmq hai senz'altro ragione.
Cmq non è di difficile implementazione, sono un ciclo *for*, 3 *if* e una
chiamata ricorsiva :)
PS: su un array di 100000 elementi:
        ~4n     ->   ~400'000 confronti
        ~nlog(n)-> ~1'150'000 confronti
non è proprio la stessa cosa :)
Ma se le prestazioni non sono importanti ... non sono importanti ;)
PPS: Bello sto thread :P
