PDA

Visualizza la versione completa : [ALGORITMO]: Ordinamento di un array


matrics
11-09-2006, 18:49
Ciao!
Ho un array di n numeri compresi fra 1 ed m
Come ordino tale array in tempo O(n log m)?

matrics
11-09-2006, 19:01
Ne ho trovato uno, il counting sort
Mi sono bruciato uno scritto :cry: :cry: :cry:

doraemon83
11-09-2006, 21:12
se vuoi il miglior algoritmo esistente per ordinare n numeri qualunque cerca il quick sort...
il piu veloce algoritmo esistente

guarda qui
http://it.wikipedia.org/wiki/Quicksort

matrics
12-09-2006, 00:05
Originariamente inviato da doraemon83
se vuoi il miglior algoritmo esistente per ordinare n numeri qualunque cerca il quick sort...
il piu veloce algoritmo esistente

guarda qui
http://it.wikipedia.org/wiki/Quicksort


ma a me serve per ordinare dei dati particolari, compresi fra 1 ed m, il quick sort usa dati generici :fagiano:


non vorrei sbagliare, ma mi pare sia meglio il mergesort, n log n al caso pessimo, di contro al quick n log n al caso medio :fagiano: :fagiano: :fagiano:

doraemon83
12-09-2006, 11:43
in effetti si il caso peggiore del quick sort n al quadrato. ma il caso peggiore un evento che si verifica molto raramente (solo quando l'array gia ordinato o ordinato in senso opposto), a differenza del caso medio.

stato dimostrato che il quick sort nel caso medio si comporta meglio di qualsiasi altro algoritmo di ordinamento, anche del merge sort. Pur avendo un comportamento asintotico uguale (n log n),
il quick sort richiede costanti moltiplicative piu piccole del merge sort, per cui considerato il migliore algoritmo di ordinamento

matrics
13-09-2006, 01:31
Originariamente inviato da doraemon83
in effetti si il caso peggiore del quick sort n al quadrato. ma il caso peggiore un evento che si verifica molto raramente (solo quando l'array gia ordinato o ordinato in senso opposto), a differenza del caso medio.

stato dimostrato che il quick sort nel caso medio si comporta meglio di qualsiasi altro algoritmo di ordinamento, anche del merge sort. Pur avendo un comportamento asintotico uguale (n log n),
il quick sort richiede costanti moltiplicative piu piccole del merge sort, per cui considerato il migliore algoritmo di ordinamento


grazie per la delucidazione :fighet:

Gigi84
13-09-2006, 23:30
essendo che il numero massimo limitato ed essendo che mi sembra un esercizio tipo da info teorica.. ;) puoi fare cos, :

Dato X, il tuo array lungo m
1) crei un array Ylungo m
2) per ogni elemento x di X
2a) Y[x] = Y[x] + 1
3) hai ordinato l'array, ovvero, Y della forma:


Y[0] = 0
Y[1] = 2
Y[2] = 1
.
.
.
Y[m] = z

e significa che in X ci sono 0 elementi uguali a 0, 2 elementi uguali a 1, i elemento uguale a 2, ..., z elementi uguali m; se vuoi un output basta che stampi, per ogni Y[i] tante i quanto vale Y[i]

se usi un criterio di costo lineare, costa O(n)
se usi un criterio di costo logaritmico costa O(nlog(m)) (perch fai Y[x] = Y[x] + 1, e sia Y[x] che x al massimo valgono m)

:)

spero di averti aiutato e di aver centrato il problema! ;)

matrics
16-09-2006, 20:10
Originariamente inviato da Gigi84
essendo che il numero massimo limitato ed essendo che mi sembra un esercizio tipo da info teorica.. ;) puoi fare cos, :

Dato X, il tuo array lungo m
1) crei un array Ylungo m
2) per ogni elemento x di X
2a) Y[x] = Y[x] + 1
3) hai ordinato l'array, ovvero, Y della forma:


Y[0] = 0
Y[1] = 2
Y[2] = 1
.
.
.
Y[m] = z

e significa che in X ci sono 0 elementi uguali a 0, 2 elementi uguali a 1, i elemento uguale a 2, ..., z elementi uguali m; se vuoi un output basta che stampi, per ogni Y[i] tante i quanto vale Y[i]

se usi un criterio di costo lineare, costa O(n)
se usi un criterio di costo logaritmico costa O(nlog(m)) (perch fai Y[x] = Y[x] + 1, e sia Y[x] che x al massimo valgono m)

:)

spero di averti aiutato e di aver centrato il problema! ;)



quello che hai scritto il counting sort, di costo lineare, non capisco come vederlo di costo logaritmico



avevo sbagliato infatti l'altro giorno, a quanto pare non serve counting sort

inoltre ho dimenticato di dire che l'algoritmo deve essere di tipo divide et impera che opera per divisioni successive su [1...M]

Gigi84
16-09-2006, 21:09
Originariamente inviato da matrics
quello che hai scritto il counting sort, di costo lineare, non capisco come vederlo di costo logaritmico


Se usi un criterio di costo costante, dove ogni istruzione ha un costo fisso e non dipende dai dati manipolaiti, il costo O(n)

se invece per valutare il costo usi un criterio di costo logaritmico, dove ogni istruzione ha un costo variabile in base alla dimensione dei dati trattati (i dati sono numeri rappresentati in binario --> dimensione = log(n)), il costo viene O(nlog(m))

:)

in questo caso comunque, essendo che i dati hanno una lughezza fissata da un limite superiore, + ragionevole utilizzare il criterio di costo costante. (dalle mie riminescenze di info teorica)

:)

matrics
16-09-2006, 21:22
Originariamente inviato da Gigi84
Se usi un criterio di costo costante, dove ogni istruzione ha un costo fisso e non dipende dai dati manipolaiti, il costo O(n)

se invece per valutare il costo usi un criterio di costo logaritmico, dove ogni istruzione ha un costo variabile in base alla dimensione dei dati trattati (i dati sono numeri rappresentati in binario --> dimensione = log(n)), il costo viene O(nlog(m))

:)

in questo caso comunque, essendo che i dati hanno una lughezza fissata da un limite superiore, + ragionevole utilizzare il criterio di costo costante. (dalle mie riminescenze di info teorica)

:)


sinceramente non ho mai fatto un'analisi di questo genere, la complessit deve essere logaritmica per come implementato l'algoritmo

Loading