[C++] Problema scrittura algoritmo

[Scara95]

Ah che poi in sostanza con il range in input hai fatto un pò una furbata perchè se i numeri sono 1 2 3 256 in realtà il tuo range è di 256 numeri ma imponendo la condizione di stampare tutti i numeri che hanno numero di occorrenze diverso da zero hai eliminato tutti i numeri da 4 a 255.

Esattamente.
Hai letto la descrizione del counting sort?

Ha complessità O(n+m) dove n è il numero di dati in input e m l'ampiezza del range. Ovvero cresce linearmente su uno dei due.

L'algoritmo proposto nell'ultimo post ha complessità O(n^2), ovvero cresce quadraticamente sul numero di dati in input.

Quale è meglio? Dipende dal numero di dati in input, dalla memoria disponibile e dal range.

n=65536 è il limite in cui si incontrano le curve su un intero a 32 bit, ma è improbabile userai sempre tutto il range di interi.

Prendiamo ad esempio i numeri da 0 a 10000, basta n=100 a far incontrare le curve, un input di 100 numeri è meno che improbabile.

[Mrhide1]

ah quindi tutta quella roba del massimo,minimo e il pezzo di algoritmo che ti avevo indicato che non capivo erano il counting sort,ammetto la mia ignoranza su questo tipo di algoritmo perchè al corso non lo abbiamo mai trattato.Ora il programma funziona perfettamente in sostanza ho fatto un misto della mia allocazione dinamica da principiante che ho postato alcuni post a dietro e la comparazione che hai fatto tu.Grazie di tutto Scara95.

[Scara95]

Di nulla, figurati