Ordinamento di un vettore

[The March]

Un po di tempo fa avevo fatto un corso nel quale, per affrontare lo stage, dovetti fare un colloquio.
il corso era su vb ma sinceramente non ne sapevamo veramente niente.
al colloquio mi chiesero di ordinare un vettore di interi in modo crescente
:eek:
nonostante non lo avessimo mai trattato nel corso (nemmeno i vettori facevano parte degli argomenti trattati nel corso) mi ci sono messo e ero riuscito a trovare una mezza soluzione....

qualcuno di voi potrebbe postarmi la soluzione?
possibilmente in vb ma se è in un'altro linguaggio va benissimo comunque!

thanks!

[cn73]

Gli algoritmi di ordinamento degli array sono fra i fondamenti di qualunque linguaggio...

Vai su google e cerca "algoritmi ordinamento array"

[The March]

Originariamente inviato da cn73
Gli algoritmi di ordinamento degli array sono fra i fondamenti di qualunque linguaggio...

Vai su google e cerca "algoritmi ordinamento array"
Thanks!
cercherò!

[PGI]

Mi sono messo nei tuoi panni e ho cercato una soluzione al problema. Non che non esistano fior fior di algoritmi per fare quello che ti hanno chiesto (pare sia un grande classico dell'informatica, con i suoi Bubble Sort, Quick sort ecc.) ma il problema è per chi, come me, di studi scientifici ne ha fatti ben pochi. Un conto è leggere l'algoritmo e tradurlo in codice, un altro è farlo su due piedi.

Da feticista, mi sono cronometrato. In 1 ora e 16 minuti ho prodotto un algoritmo non ricorsivo di rara inefficenza, che però ha il pregio di essere un parto dei due o tre neuroni che ancora rimangono attivi.

Il primo problema che ho affrontato è quello di trovare in un vettore di numeri il numero minore.

in pseudo-pseudo codice, la faccenda l'ho risolta così:


intero X = vettore.primoElemento;
intero INDICE = 0;

ciclo:
per ogni numero N nel vettore, a partire dal secondo:

se X è maggiore di N -> INDICE = indice_di_N
fine ciclo.


dopo il ciclo, INDICE è diventato l'indice del numero più piccolo all'interno del vettore.

Con grande stupore di me stesso, ho scoperto che a questo punto i giochi erano già fatti.

Bastava rimuovere dal vettore originale il numero più piccolo ed infilarlo in coda ad un secondo vettore, che contenesse i numeri "ordinati": a questo punto infatti il vettore originale, avendo perso l'elemento più piccolo tra quelli contenuti, sarebbe stato già pronto per un nuovo passaggio alla ricerca del numero minore.

quindi, se N è il numero di elementi del vettore originale, l'algoritmo completo diventa


vettore
cache

ciclo esterno da 0 a N:
intero X = vettore(0);
intero indice = 0;

ciclo interno da J = 1 a J = vettore.dimensione:
intero Y = vettore(J);
se (X > Y) -> indice = J; X = Y;
fine ciclo interno

vettore.rimuovi(elemento_indice);
cache.aggiungi(elemento_eliminato);
fine ciclo esterno.


In Java la cosa assume la seguente forma:


Vector<Integer> vettore = //vettore con i numeri
Vector<Integer> cache = new Vector<Integer>();
int numLoops = vettore.size();
for(int loop = 0; loop < numLoops; loop++) {
int size = vettore.size();
int valore = vettore.get(0);
int indiceMinore = 0;

for(int i = 1; i < size; i++) {
int valore2 = vettore.get(i);
if(valore > valore2) {
valore = valore2;
indiceMinore = i;
}
}
cache.add(vettore.remove(indiceMinore));
}


In VBasic sono certo che i vettori abbiano un comportamento analogo: in Java "get(int)" restituisce (ma non rimuove) il valore dell'elemento di indice "int", "remove(int)" restituisce e rimuove l'elemento di indice "int", "add(valore)" aggiunge in coda al vettore "valore".

Se cerchi in rete per "Bubble Sort" o "Quick Sort" trovi la soluzione "reale" al problema.

Ciao.

[cn73]

Di algoritmi per l'ordinamento ne esistono un bel po', ognuno coi suoi pregi e i suoi difetti...

Algoritmi di ordinamento per array:
Insertsort.
Selectsort.
Bubblesort.
Heapsort.
Quicksort.
Mergesort.

http://www.sti.uniurb.it/info_appl_liv1/programmi/algo_stru_dati.html

PGI puoi sopperire alle tue mancanze teoriche studiando i pregi e i difetti di ognuno, e soprattutto la complessità computazionale:


La complessità computazionale si occupa della valutazione del costo degli algoritmi in termini di risorse di calcolo, quali il tempo di elaborazione e la quantità di memoria utilizzata. Nel contesto della complessità computazionale vengono anche studiati i costi intrinseci alla soluzione dei problemi, con l'obiettivo di comprendere le prestazione massime raggiungibili da un algoritmo applicato a un problema." (Cadoli)


http://digilander.libero.it/unno2/sort/complessita.htm

Se ho imparato a conoscerti un minimo questa cosa ti farà sbiellare :D

[The March]

Grazie per il codice!

io dovevo farlo in un colloquio e non ho avuto tutto questo tempo, ma in 20 minuti con un po di aiutini, per lo più inutili, sono riuscito a fare un codice scandaloso ma almeno funzionante!
al contrario degli altri io sono riuscito a finirlo! (forse è per questo che ora ti sto scrivendo dall'ufficio)

[PGI]

Originariamente inviato da cn73
Se ho imparato a conoscerti un minimo questa cosa ti farà sbiellare :D

Colpito e affondato :D, stavo proprio cercando, due minuti dopo aver scritto il codice, un pagina che spiegasse la complessità degli algortimi :D

[ri]

std::vector<int> v;
// carico v
std::sort(v.begin(), v.end());


facile facile :asd:

come han già detto cmq gli algoritmi di ordinamento sono la base di qualsiasi corso di programmazione
è caldamente consigliato un loro studio ;)

[The March]

Originariamente inviato da ri

std::vector<int> v;
// carico v
std::sort(v.begin(), v.end());


facile facile :asd:

come han già detto cmq gli algoritmi di ordinamento sono la base di qualsiasi corso di programmazione
è caldamente consigliato un loro studio ;)


Purtroppo il corso al quale mi ero iscritto era veramente Scandaloso in quanto ad argomenti trattati

esempio?

avevamo due materie sui database e l'unica cosa che sapevo fare era una select semplice senza join e basta!
il nome del corso? "sviluppatore applicazioni client/server"

[Fenomeno85]

ne esistono di diversi tipi l'importante è chè sai come funzionano, dopo il codice è semplice da scrivere.

~§~ Sempre E Solo Lei ~§~