[ALGORITMO]: Ordinamento di un array

[matrics]

Ciao!
Ho un array di n numeri compresi fra 1 ed m
Come ordino tale array in tempo O(n log m)?

[matrics]

Ne ho trovato uno, il counting sort
Mi sono bruciato uno scritto

[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

[matrics]

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


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

[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

[matrics]

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

[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!

[matrics]

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]

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]

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