Ordinare una lista

[jimmy_delirio]

Scusate ma non ne vengo fuori!!!!

Ho una lista concatenata

mettiamo che *testa punti sempre al primo elemento, *coda punti sempre all' ultimo elemento. All' interno di ogni nodo c'è un intero.

*scan lo uso per scandire la lista
*scan->next ne è il successivo

Utilizzando un qualsisi algoritmo di ordinamento (quicksort,mergesort...) come ordino i nodi in ordine crescente?

Grazie

[Zero-2]

Non puoi usare quicksort o mergesort su di una lista , perchè non puoi accedervi in maniera casuale , ma solo sequenziale.
Li puoi ordinare o man mano che li inserisci oppure devi usare un algoritmo lineare di ordinamento .

[jimmy_delirio]

che algoritmo lineare ad esempio?

grazie

[Zero-2]

Potresti servirti di una seconda lista ed inserire in modo ordinato i nuovi elementi.

Del tipo

public void ordina(Lista p){
Lista l=new Lista();
Iterator it=p.getIterator();
while(it.hasMore()){
l.insOrdinato(it.next());
}
}

dove insOrdinato è un metodo di lista che ti permette di ordinare una lista man mano che la inserisci.
Sennò puoi inserire gli oggetti presenti nella lista in un array e ordinarlo come ti pare , successivamente ricopiare l'array in una uova lista .

[zaion]

al posto di una lista concatenata potresti usare un albero binario.
con gli alberi quando metti dentro un elemento viene ordinato automaticamente. bello no.

[Zero-2]

La mia non è l'unica soluzione

[jimmy_delirio]

La mia lsta è in realtà una lista di liste e io devo ordinare i nodi in base all' intero sulla verticale:

intero--->nodo---->nodo---->nodo
|
|
intero--->nodo---->nodo---->nodo
|
|
intero--->nodo---->nodo---->nodo
|
|
intero--->nodo---->nodo---->nodo

ferrmo restando che i puntatori alla lista orizzontale debban oessere mantenuti. LE soluzioni che mi avete proposto vanno ancora bene no?

[alexfin]

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

[butchertkd]

nonostante il thread sia vecchio di più di otto anni, provo lo stesso...

- 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)

ho fatto senza problemi i primi due punti..ma ho dei problemi nel modificare i puntatori della lista..

ho fatto una funzione del genere

void AdjustList(node* *p,char* *a){
     if (*p != NULL){
         node **nxt = &((*p)->next);
         *p = (node*) *a;
         (*p)->next = *nxt;
         AdjustList(nxt, a + 1);
     }
     return;
} 

una funzione che prende la lista (come puntatore di puntatore a nodo (per modificare il puntatore))
e l'array di puntatori.. nella visita salvo il successivo corrente poi cambio l'indirizzo del nodo corrente con quello ordinato nell'array, nel successivo del nodo appena cambiato vado a mettere il successivo salvato precedentemente, per non saltare nodi, e richiamo ricorsivamente la funzione...
l'output è un segmentation fault..cosa sbaglio?? lo scopo è puramente didattico, per prendere mano con i puntatori.

[butchertkd]

risolto...così..e l'ultimo valore dell'array è NULL..

void AdjustList(node* *p,char* *a){
     while(*a != NULL){
         node *nxt = (*p)->next;
         *p = (node*) *a;
          (*p)->next = nxt;
         p = &((*p)->next);
         a++;
     }
     *p = NULL;
     return;
 }