Newsgroup: it.comp.lang.visual-basic
Titolo: Ordinamento Array (queicksort con parametri)

Dunque, ho un array di elementi definiti da un tipo così fatto:
Private Type CharXY
    Carattere As String
    X As Long
    Y As Long
End Type
Ora mi interesserebbe ordinare in base alle y (priorità) e successivamente
nell'ambito delle y ordinare in base alle x (per capirci, in SQL sarebbe una
semplice Order By Y,X)
Con quicksort riesco ad ordinare solo in base ad un parametro... ma per 2
parametri?
grazie
bye
-- 
Esistono 10 tipi di persone: chi conosce il binario e chi no.
"Seminate Linux, che Windows si pianta da sè...." (Antico Adagio)
Gestione Ottica - Gestionale per Ottici e Programmi Gratuiti su:
http://www.nicolaottomano.it
Sinapsi Antispam. Antispam Gratuito.
http://www.nicolaottomano.it/public/SinapsiAntispam-Setup.exe
email spamtrap: 
spam...@nicolaottomano.it

 parametri?
Bella domanda.
Me lo sono chiesto anch'io in passato e l'unica soluzione che ho trovato è
stata rendere i due parametri uno solo.
es.
' La prima soluzione che mi è venuta in mente,
' probabilmente ottimizzabile
Dim buffer1(0 to 7) As Byte
Dim buffer2(0 to 7) As Byte
Dim pippo1 as CharXY
Dim pippo2 as CharXY
...
' e qui controlla i ByVal che mi confondo sempre
copymemory(ByVal buffer1(0), ByVal pippo1.X, 4)
copymemory(ByVal buffer1(4), ByVal pippo1.Y, 4)
copymemory(ByVal buffer2(0), ByVal pippo2.X, 4)
copymemory(ByVal buffer2(4), ByVal pippo2.Y, 4)
' confronto
for i = 0 to 7
    ret = buffer1(i) - buffer2(i)
    if (ret <> 0) then
        exit for
    end if
next
if (ret < 0) then
    Debug.Print "pippo1 < pippo2"
elseif (ret > 0) then
    Debug.Print "pippo1 > pippo2"
else
    Debug.Print "pippo1 = pippo2"
end if
Tempo fa, sempre lavorando sui puntatori avevo fatto un QuickSort simile a
quello C, che poteva ordinare variabili di qualsiasi tipo, senza la
necessità di farsi 80 qs tipizzati.
Ma non ricordo nemmeno se l'avevo finito :P
Ciao
-- 
NeoDataType : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net

 stata rendere i due parametri uno solo.
[SNIP]
Se i parametri sono numerici, come in questo caso, e se i valori che possono
assumere x e y non sono esageratamente grandi, e' possibile farlo piu'
semplicemente moltiplicando il primo valore per un coefficiente alto
(utilizzando Currency o Decimal come tipo di dato temporaneo) e sommandolo
al secondo.
Ciao
--
Luca Dormio - 
luca....@tin.it
________________________________
"Marty, non stai ragionando in maniera quadridimensionale"
Dr. Emmett L. Brown

 ha scritto nel messaggio
news:MaNld.8419$
n%2.3...@tornado.fastwebnet.it

Ci ho pensato, ma mi sembrava troppo stupido.... ci deve essere qualcosa di
più sexy... vorrei tanto sapere come funziona l'ORDER BY di SQL...
Comunque credo che procederò nel modo "grezzo".


 parametri?
Quicksort prima sulla y, poi per ogni y (fissato) quicksort sulla x.
ciao
	maxx
-- 
NOSPAM: Rimuovere i trattini dallo username!
Cut hyphens from my username!

 Quicksort prima sulla y, poi per ogni y (fissato) quicksort sulla x.
Ci avevo pensato ma le prestazioni scendono paurosamente... tieni conto che
sto facendo una funzione di OCR. E il testo può raggiungere centinaia (o
migliaia) di caratteri.
Credo che per questa volta implementerò la soluzione "grezza".
Cmq grazie.


In genere io faccio:
V -> Vettore (1..N)
For I = 1 To N
   For J = I + 1 To N - 1
     If V(I) > V(J)
       Temp = V(I)
       V(I) = V(J)
       V(J) = V(N)
     End If
   Next J
Next I
Per il tuo caso potresti fare:
Dim Flag As Boolean
For I = 1 To N
   For J = I + 1 To N - 1
     If V(I).X >= V(J).X Then
       If V(I).X > V(J).X Then
          Flag = True
       Else
          If V(I).Y > V(J) Then Flag = True
       End If
       If Flag Then
          Temp = V(I)
          V(I) = V(J)
          V(J) = V(N)
          Flag = False
       End If
   Next J
Next I
Ma non so come vada a prestazioni... fammi sapere :)
-- 
Quando noi ignoranti eravamo di piů, tutto era piů bello (A. Celentano).
  ___   _   ___ _  _______   _______ ___
|   \ /_\ | _ \ |/ / _ ) \ / /_   _| __|
| |) / _ \|   / ' <| _ \\ V /  | | | _|
|___/_/ \_\_|_\_|\_\___/ |_|   |_| |___|
--
X-Privat Project - 
http://www.newsserver.it/

          If V(I).Y > V(J) Then Flag = True
Errore mio...
            If V(I).Y > V(J).Y Then Flag = True
-- 
Quando noi ignoranti eravamo di più, tutto era più bello (A. Celentano).


 Ma non so come vada a prestazioni... fammi sapere :)
Mi pare il caro, vecchio, Bubble Sort... sul centinaio di elementi puo' 
anche andare, altrimenti le prestazioni affondano drammaticamente.


 grazie
Non ricordo se quicksort ha questa caratteristica (oggi sono smemorato),
ad ogni modo il tuo problema si risolve ordinando prima per Y (con
qualsiasi algoritmo) e successivamente per X (una sola volta sull'array
totale già ordinato per Y) con un algoritmo che ha questa simpatica
caratteristica.
termoPilucco
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 caratteristica.
La caratteristica di cui parlavo (e di cui non trovo il nome) consiste
nell'ordinare mantenendo l'ordine originale dei "record" nel caso la
chiave sia uguale.
ES: ordino (x,y) per x:
da (2,5) (2,1) (1,7) --> (1,7) (2,5) (2,1) e non (1,7) (2,1) (2,5) perchè
in origine c'era prima (2,5) poi (2,1).
Se quicksort la supporta sei a posto.


 Se quicksort la supporta sei a posto.
No, purtroppo quicksort non è stabile.
Ciao.
-- 
BSD is for UNIX lovers -- linux is for Windows haters.

 
Mi sfugge l'utilita' di questa caratteristica nel caso specifico.
L'ordinamento, se non ho capito male la richiesta di Nicola, dovrebbe 
consistere nell'ordinare per la prima variabile e poi per la seconda 
variabile quando la prima ha lo stesso valore.
Anche mantenendo l'ordine originale quando ordino per la seconda 
variabile otterrei:
(2,1) (2,5) (1,7)
Ma forse mi sfugge qualcosa...


 No, purtroppo quicksort non è stabile.
Ecco, quindi si usa quicksort per il primo ordinamento (y) e poi un
algoritmo stabile per eseguire il secondo (x)


 Ma forse mi sfugge qualcosa...
Infatti bisogna ordinare prima la seconda variabile e poi al prima :)
sequenza orginale:
(2,5) (2,1) (1,7)
ordino per y (uso qualsiasi algoritmo)
(2,1) (2,5) (1,7)
ordino per x (uso un algoritmo "stabile")
(1,7) (2,1) (2,5) 
l'algoritmo "stabile" garantisce che (2,1) verrà prima di (2,5) perchè
nell'array passato era così.


termoPilucco ha scritto:
Due algoritmi di ordinamento stabili:
Radix sort e Mergesort
qui c'è una implementazione VBA del primo:
http://groups.google.it/groups?hl=it&lr=&selm=eKpeLSFvEHA.1300%40TK2MSFTNGP14.phx.gbl&rnum=5


Ho dimenticato di ringraziare termoPilucco per li link.
M sarą utile per altre cose che ho in mente.
bye
-- 
Esistono 10 tipi di persone: chi conosce il binario e chi no.
"Seminate Linux, che Windows si pianta da sč...." (Antico Adagio)


Scusate se mi intrometto... non conosco gli algoritmi di ordinamento se 
non il quicksort da me citato poco fa.
Perň gli algoritmi, in genere, non sono progettati per una sola variabile?
Nell'esempio numerico di termopilucco:
(2,5), (2,1), (1,7)
se lo ordino (con qualsiasi algoritmo) secondo y:
(2,1), (2,5), (1,7)
se poi con lo stesso algoritmo ordino secondo x che accade se non č 
"statico"?
Perchč dovrebbero miscelarsi? o_O
Forse dovrei dare un'occhiata alla definizione di "statico", ma intando 
attendo delucidazioni perchč ci son rimasto un po' spaesato :)
-- 
Quando noi ignoranti eravamo di piů, tutto era piů bello (A. Celentano).


 parametri?
Basta che quando fai il confronto fra i due elementi tieni conto di
entrambi i campi:
dati due CharXY (c1 e c2)
c1 < c2 se
c1.Y < c2.Y
o se 
c1.Y = c2.Y e c1.X < c2.X
In questo modo fai un ordinamento come vuoi tu.


 Perchè dovrebbero miscelarsi? o_O
In questo caso, con soli tre elementi, il problema non si presenterà
neppure, ma quando gli elementi sono molti le cose cambiano.
Tra l'altro non è detto che non venga mantenuto l'ordine, dipende da
come sono gli elementi e da come sono disposti.
Però un algoritmo stabile garantisce che quest'ordine venga mantenuto,
mentre con un algoritmo non stabile si va a fortuna...


Grazie per la delucidazione :D
-- 
Quando noi ignoranti eravamo di più, tutto era più bello (A. Celentano).


 In questo modo fai un ordinamento come vuoi tu.
si questa sarebbe una buona idea, non ci avevo pensato...
Comunque ho notato che utilizzando il BubbleSort (termiPilucco non me ne voglia
http://snipurl.com/anm5
 ) il rapporto risorse allocate/prestazioni è molto buono (anche meglio del
quicksort ecc...). Qualche post fa ho detto che i caratteri potevano essere migliaia, ma in realtà
(con piccoli accorgimenti) si può ridurre una intera email a 40/50 caratteri sul quale fare
ordinamento.
 L'unico algoritmo sul quale ho alcuni dubbi (nel senso che mi sembra allochi poco e sia veloce) è
il LinearSort di termoPilucco.
Inoltre ho provato il test sugli algoritmi di Sort presenti sul SC e mi sono fatto alcune idee.


attendo delucidazioni perchč ci son rimasto un po' spaesato :)
Meglio che cerchi il termine "stabile" :)
termoPilucco

il LinearSort di termoPilucco.
LinearSort alloca poca memoria solo se la distanza tra il valore minimo e il
valore massimo dei dati da ordinare č piccola, altrimenti sono ca@@i.
Se ordini un miliardo di elementi con valori tra 1 e 100 il linear sort alloca
100 long ed esegue un miliardo e 100 operazioni (da cui, appunto, il nome
linear).
Se ordini due soli elementi "1" e "un miliardo", il linear sort allocherebbe
1.000.000.000 di long (da cui, appunto, termoPilucco va a nascondersi).
In effetti la versione finale cha avevo scritto previene i casi sfavorevoli e
chiama in suo aiuto quicksort  :) 
In pratica va usato solo se si conosce bene la natura dei dati che si vogliono
ordinare.
termoPilucco

 vogliono ordinare.
Si ho visto la chiamata alla quicksort. L'algoritmo l'ho trovato guglando su alcuni vecchi post.


 Non ho ben capito il senso della cosa. Potresti farmi un esempio
allora:
prendiamo un array V= (7,6,5,5,3,9,4,7,6,5)
numero elementi=10
il min è 3
il max è 9
9-3=6 = long allocati da algoritmo per array di appoggio (sempre che tu
abbia la versione di linearsort che normalizza i dati al valore minimo).
Passi eseguiti durante l'elaborazione= 10 + 6. 
Quicksort dovrebbe girare in N*log2(N)=10*4=40
Bubble Bobble Sort dovrebbe girare in N*(N-1)=10*9=troppo
L'algoritmo conviene :)
prendiamo un array W con due soli elementi (1, 1.000.000.000)
numero elementi=2
il min è 1
il max è 1.000.000.000
1.000.000.000-1 = 999.999.999 = long allocati da algoritmo per array di
appoggio.
Passi eseguiti durante l'elaborazione= 2+999.999.999
Passi eseguiti da qualsiasi altro algoritmo: 2
L'algoritmo non conviene :)


 Comunque ho notato che utilizzando il BubbleSort...
[...]
Beh, il "metodo" che ti ho suggerito è indipendente dall'algoritmo
usato, seve solo per implementeare la funzione di confronto.
