PDA

Visualizza la versione completa : [ALGORITMO] Ordinamento con Linked List


Celebron
06-01-2011, 16:20
Riscrivo la domanda in un post a se in quando, nella discussione in cui la avevo precedentemente messa, non era totalmente attinente

Ho ripreso in mano una vecchia libreria che avevo fatto proprio sulle linked list, e ho notato la funzione di ordinamento che non mi convince proprio

la dovrei aver sicuramente sviluppata basandomi su quanto suggeriva il Sedgewick in merito, visto che era quello il manuale di algoritmi legato al corso. Nella pratica si basa su una lettura di tutta la lista individuando ogni volta l'elemento minore e attaccandolo ad una seconda lista ausiliaria. Sebbene questo porti a non dare problemi di memoria (aggiunge semplicemente un putantore testa temporaneo) a mio parere, essendo una sorta di selection sort, per grandi moli di dati diventa troppo lento.
Ora sebbene sia consapevole che le liste di solito andrebbero usate quando non sono previsti numerosi ordinamenti, mi chiedevo se fosse da privilegiare una risoluzione di questo genere (la lista è formata da node_t*nodo che contengono i campi item_t*obj e node_t*next):
converto temporaneamente la lista in un vettore di item_t*, mentre durante la creazione del vettore faccio il free() dei vari nodi in modo che l'occupazione di memoria resti pressoché uguale (anzi, risparmio la memoria dedicata ai puntatori a next dei node_t*), quindi lancio un quicksort sul vettore e infine ricompongo la lista liberando la memoria occupata dal vettore

Alla fin fine avrei un costo in termini di tempo n+1 costante dato dalla creazione del vettore e dalla sua distruzione, riducendo però la complessità dell'ordinamento da (n^2)/2 a n*log(n). In questo caso il costo costante aggiuntivo dovrebbe risultare trascurabile.
Ho sbagliato qualcosa?

Loading