Newsgroup: it.comp.programmare
Titolo: Re: ordinare un array?

 thanks!!!
in che linguaggio?
Plausibilmente la tua libreria avrà una funzione sort o qsort per farlo.



-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
johann...@libero.it
 wrote:
| qual'č il modo + efficente per ordinare un vettore? ci sono dentro
| anke numeri negativi!!! usando il rudimentale ASSEMBLY Language?
| thanks!!!
L'algoritmo piu' semplice e' senza dubbio il bubble-sort ma ha
complessita' n^2, il che non lo rende molto efficiente; infatti e' un
modo elegante per confrontare uno ad uno ogni elemento con tutti gli altri.
Il piu efficiente credo sia il quick-sort (con complessita' n*log(n)),
ma e' ricorsivo, il che lo rende, non impossibile, ma difficile da
implementare in assembler.
Esiste anche il selection-sort e mi sembra che sia facilmente
implementabile sia in modo ricorsivo che iterativo, ma non credo abbia
notevoli pregi oltre al fatto di essere intuitivo (in pratica scegli un
elemento e lo confronti con gli altri, poi ne scegli un altro, etc...)
Segue una (spero comprensibile) descrizione in italiano dei due
algoritmi piu' usati, a te la traduzione in assembler.
BUBBLE-SORT:
Devi tenere due indici uno alla cima dell'array (dove posizionerai il
numero piu' piccolo) e uno in fondo (dove posizionerai il numero piu'
grande).
1. Confronti il contenuto in corrispondenza dei due indici, se quello in
cima e' piu' grande di quello in fondo, li scambi.
2. Incrementi il 'puntatore' alla cima (avvicinandolo al fondo, quindi),
se e' minore dell'indice finale vai al punto 1 altrimenti vai al punto 3
3. Riazzeri il 'puntatore' alla cima e decrementi il 'puntatore' al
fondo (escludendo percio' l'ultimo elemento che ormai e' gia'
posizionato). Se il 'puntatore' al fondo punta al secondo elemento
termina, altrimenti torna al punto 1
QUICK-SORT:
definisco:	sup -> l'indice del primo elemento
		inf -> l'indice dell'ultimo elemento
Scelgo un elemento a caso dell'array detto perno (tipicamente quello
centrale ma e' *indifferente*) il cui indice lo chiamo k.
Faccio in modo che nella parte prima del perno ci siano _esclusivamente_
elementi minori del perno e nella parte dopo il perno ci siano
_esclusivamente_ elementi maggiori del perno [1]. Applico ricorsivamente
l'algoritmo alle due porzioni di array da sup a k e da k+1 a inf.
[1] ad esempio cosi:
1. Scorri la parte prima del perno (da sup) fino a trovare un elemento
maggiore del perno. memorizzane l'indice
2. Scorri la parte dopo il perno (da inf) fino a trovare un elemento
minore del perno. memorizzane l'indice.
3. Scambia i due elementi trovati e prosegui fino a quando i due
puntatori utilizzati per scorrere in senso opposto l'array non si
incrociano (NB: e' possibile spostare anche l'elemento perno!)
Spero di esserti stato utile,
Paolo
Ps: Se avessi qualche problema con la decifrazione dei miei scritti, non
esitare a chiedere; comunque il materiale a riguardo abbonda su internet
e, adesso, sai cosa cercare ;-)
- --
Anche se detesto quello che dici
difendero' fino alla morte il tuo diritto a dirlo
~ - Voltaire
/\/ / /-/ / /_    Copyleft 1984. All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - 
http://enigmail.mozdev.org
iD8DBQFBwh0+S9pqiAxcD1kRAlNnAJsExTj052Ot2H1f+Rer3OB6EePi+wCfWTJm
VwqKUuuVs7ghGv1kUUyPZXI=
=WXkN
-----END PGP SIGNATURE-----