Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Algoritmi di ordinamento consigli
Forum - C/C++ - Algoritmi di ordinamento consigli

Avatar
oretovalley (Normal User)
Pro


Messaggi: 109
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 19:23
Mercoledì, 22/07/2009
Ciao a tutti, guardando i vari è più famosi algoritmi di ordinamento, volevo sapere quale secondo voi è il migliore in termini di complessità computazionale, ma anche in termine di velocità, inoltre qualora io volessi sviluppare un'ordinamento come potrei fare per calcolare la velocità in confronto con gli altri. Vi ringrazio delle risposte che mi darete.

PM Quote
Avatar
Lawliet (Normal User)
Expert


Messaggi: 386
Iscritto: 09/04/2009

Segnala al moderatore
Postato alle 20:05
Mercoledì, 22/07/2009
http://it.wikipedia.org/wiki/Algoritmo_di_ordinamento

Qui sta la tabella con la formula dei calcoli possibili di ordinamento dal migliore al peggiore. Non credo che esista uno migliore rispetto agli altri, ma penso invece che ogni algoritmo è efficiente in base al problema che ti trovi davanti. Il più semplice penso che sia quello a inserimento o bubble sort.


"Dai un pesce (programma) a un uomo e lo nutrirai per un giorno. Insegnagli a pescare (programmare) e lo nutrirai per tutta la vita." (niente pappa pronta)
cit. theprogrammer
PM Quote
Avatar
oretovalley (Normal User)
Pro


Messaggi: 109
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 20:34
Mercoledì, 22/07/2009
Ottimo, programmando ho tirato su un codice di ordinamento molto banale, potete dirmi se gia esiste questo tipo di algoritmo(sicuramente si vista la semplicità), è soprattuto come vi sembra a livello di complessita computazionale:

Codice sorgente - presumibilmente C++

  1. void ordinavettore(int *vettore, int numero) {          
  2.      int indice = 1, k = vettore[0], contatore = 0, pos = 0;    
  3.      do {                    
  4.         for(;indice < numero; ++indice) {
  5.                  if(k > vettore[indice]) {
  6.                       k = vettore[indice];
  7.                       pos = indice;
  8.                  }                
  9.         }
  10.         vettore[pos] = vettore[contatore];  
  11.         vettore[contatore] = k;    
  12.         contatore += 1;
  13.         k = vettore[contatore];
  14.         indice = contatore + 1;              
  15.      }while(contatore < numero - 1);    
  16. }


Ultima modifica effettuata da oretovalley il 22/07/2009 alle 20:34
PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 1:33
Venerdì, 24/07/2009
a occhio e croce mi sembra un algoritmo di ordinamento per selezione.

ossia selezioni l'elemento più grande all'interno del sotto-vettore e poi lo poni in testa allo stesso, il tutto per n-1 volte.

PM Quote
Avatar
oretovalley (Normal User)
Pro


Messaggi: 109
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 11:17
Venerdì, 24/07/2009
esatto, è a parita di fattori, sembra che quest'ultimo sia più veloce del quicksort, il mio tentativo è stato provato generando in entrambi i casi 1000 numeri casuali e automaticamente ordinarli, il quicksort risulta più lento di quest'ultimo che in caso di molti numeri mi sembra molto più prestante, quindi volevo sapere quali sono i più veloci algoritmi di ordinamento per vedere la differenza con il mio.

PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 13:03
Venerdì, 24/07/2009
beh, non esiste un algoritmo di ordinamento "migliore" dato che ci sono casi dove funziona meglio uno rispetto ad un altro.

per ordine di complessità tra i migliori vi sono il quicksort e il mergesort entrambi con complessità pari O(nlogn)

ovviamente vi sono casistiche ove il mergesort funziona meglio del quicksort.

il selection sort è un algoritmo con complessità O(n^2), quindi sulla carta, per così dire, è migliore il quicksort, tuttavia vi sono casi in cui il quicksort, per via della distribuzione di elementi da ordinare, finisce per avere la stessa efficacia di un algoritmo con complesità O(n^2)

comunque, e qui parlo per esperienza, se davvero vuoi raffrontare il tuo algoritmo con il quicksort prova a farlo su un quantitativo molto superiore al milione di elementi, questo per notare meglio le differenza in quantitativo di tempo.

PM Quote
Avatar
netarrow (Admin)
Guru^2


Messaggi: 2502
Iscritto: 12/05/2004

Segnala al moderatore
Postato alle 14:08
Venerdì, 24/07/2009
bisogna anche assicurarsi di usare la versione randomizzata di quick sort.
usando questa le probabilità di avere casi tendenti a n^2 sono bassissime (se poi i numeri sono tanti praticamente nulle).

il quick sort non conviene usarlo quando hai maggiori informazioni sui dati, se sai che sono sotto struttura di heap ad esempio è meglio usare heap sort, se sai che i numeri stanno in un range da 0 a k puoi usare il counting-sort che ha complessità lineare o il radix-sort.
per quanto riguarda il merge sort bisogna anche considerare che non ordina in loco rispetto il quick sort.

cmq gli algoritmi per seleziona sono tra i peggiori, a meno che non si appoggino su strutture dati che rendano più facile la ricerca del massimo e del minimo, ad esempio nella max-min-heap.

ora come ora il quick-sort, in generale, è il miglior algoritmo di ordinamento, e per quanto riguarda gli algoritmi basati su confronti è dimostrato che meglio della complessità nlogn non può andare.



Mai memorizzare quello che puoi comodamente trovare in un libro.
Imparare è un'esperienza; tutto il resto è solo informazione.
L'immaginazione è più importante della conoscenza.
(A. Einstein)


Esistendo poi google...
PM Quote
Avatar
eddiewrc (Member)
Expert


Messaggi: 560
Iscritto: 30/04/2006

Segnala al moderatore
Postato alle 18:58
Domenica, 09/08/2009
è dimostrato matematicamente dal teorema "Lower Bound per Comparison sort" che un algoritmo basato su confronti (comparison, appunto), non può avere una complessità inferiore a nlog(n).

quicksort è inoltre il più veloce tra gli algoritmi di questo genere, per cui mi pare strano (senza offesa) che il tuo abbia prestazioni migliori.

così a occhio direi che per fare i test usi la versione RICORSIVA di quicksort... ho indovinato?

tutti i salvataggi dei parametri sullo stack che deve effettuare per compiere tutte le chiamate ricorsive necessarie a ordinare 1000 numeri pregiudicano la velocità intrinseca dell'algoritmo. prova a confrontarlo con la versione iterativa di qsort e dicci il risultato! inoltre come ha detto netarrow usa un pivotaggio casuale perchè altrimenti l'albero delle ricorsioni/iterazioni risulta sbilanciato e il costo diventa assimilabile a quello di insertion sort, che non è proprio eccezionale!



La conoscenza non ha mai fatto del male a nessuno. Caso mai hanno fatto del male quelli che hanno impiegato MALE la loro conoscenza. La conoscenza deve essere libera e quando dico libera intendo "free as freedom" e non "free as a free beer".
PM Quote