perchè non crei un vettore di liste e ordini il vettore normalmente ??? La lista di liste sarà anche bellina da dire ma non è proprio il massimo dell'efficienza... per accedere all'ultimo elemento dell'ultima lista ci metti un bel po' !!!
Comunque si può adattare il quick anche ad una lista, procedendo così:
- ti crei un vettore di puntatori(agli elementi della lista) e ci scrivi dentro gli indirizzi degli elementi della lista, così com'è, visitandola semplicemente (complessità lineare)
- ordini il vettore di puntatori (complessità = complessità dell'algoritmo di ordinamento)
- modifichi i puntatori della lista visitando uno ad uno gli elementi così come sono ordinati nel vettore (complessità lineare, c'è solo da modificare un paio di puntatori ogni elemento)
Il tutto dovrebbe avere complessità O ( n + n logn + n ), quindi ok, e utilizzare n*4 bytes di memoria
Il rovescio della medaglia è che ordinare una lista in effetti non serve a niente !!! Un qualsiasi algoritmo di ricerca non farà altro che visitare la lista da cima a fondo finchè non trova il valore cercato, la complessità è un O (n) comunque, anche se la lista è ordinata!!! L'unico vantaggio sarebbe un miglioramento nelle ricerche senza successo, che nel caso peggiore resterebbe comunque O (n).
Non a caso sono stati inventati gli alberi bilanciati !!!