[C] qsort() e algoritmi di ordinamento

[Atem1]

Salve ragazzi, io avrei una domanda sul quicksort ed in particolare sulla funzione qsort().
Sto facendo un esercizio che chiede di leggere delle parole da un file (che ne contiene 104890) e le richieste sono di ordinare queste parole con:
a)quicksort
b)quicksort ottimizzato
c)qsort()
Su a) e b) non ho problemi, ma avrei una curiosità sulla c)
La richiamo così:

qsort(parole, n, sizeof(char*),confr);

Voglio implementare confr
Scrittura 1:

int confr(const void *a,const void *b)
{
return strcmp(*(char **)a,*(char **)b);
}

Scrittura 2:

int confr(char **a, char**b)
{
return strcmp(*a,*b);
}

Io ho svolto l'esercizio con la scrittura 2, mentre nella soluzione dell'esercizio c'è la scrittura 1.
La mia domanda è se queste 2 scritture sono equivalenti o se c'è qualche ragione per cui è più conveniente usare la 1.
Grazie mille per l'attenzione

[Atem1]

"apatriarca":Bhe, la chiave del nuovo albero sarebbe ricorrenza e nome insieme. Ordini prima in base alla ricorrenza e poi in base al nome..

Wow grazie mille, a questo non avevo pensato.
Però rimane sempre il problema del mergesort/quicksort.
Senza usare il mergesort/quicksort sarebbe facile passare da un albero all'altro usando questa nuova chiave, ma il mergesort/quicksort come glielo applico? Io so applicare il mergesort appoggiandomi ad un file, ma se non ho capito male, claudio86 nel suo ultimo post ha detto che è impossibile applicare uno di questi 2 ordinamenti ad una struttura ad albero.
In effetti l'albero di ricerca binario è già di per sè una struttura ordinata quindi è normale che non abbia senso applicare il mergesort/quicksort all'albero sebbene io voglia ordinarlo secondo un criterio diverso.
Avrei potuto trasferire i dati dell'albero a quelli di una lista normale e poi applicargli l'Insert Sort per liste ma l'esercizio mi costringe ad usare il mergesort o il quicksort quindi anche questa cosa non posso farla o per lo meno io non ho la più pallida idea di come poter applicare mergesort/quicksort alle liste.
Dunque ne deduco che l'esercizio, anche se non dice espressamente che devo usare un file, implicitamente mi costringe comunque a farlo.
Comunque sicuramente questo consiglio sulla chiave composta mi sarà utile per il futuro visto che non ci avevo pensato

[Atem1]

Cioè intendo dire che l'esercizio non mi lascia la libertà di decidere come ordinare in base alle ricorrenze.
L'esercizio vuole espressamente che io usi il mergesort o il quicksort ma senza usare array o matrici.

[apatriarca]

Non vedo alcun riferimento all'uso di mergesort o quicksort nel testo dell'esercizio che hai postato.. Usando gli albero è già tutto ordinato. Ma se proprio devi usare questi algoritmi, il mergesort non ha bisogno di accesso casuale e può essere implementato per le liste concatenate.. Sono una soluzione migliore di quella di scrivere su file..

[Atem1]

Penso che quando dica "algoritmo di complessità logaritmica" si riferisca e mergesort/quicksort.
Ma comunque come si applica il mergesort alle liste?
Il passaggio che mi fa riflettere è quello di dividere in due la lista.
Visto che la lista non è una struttura ad accesso casuale l'unico modo per trovare il punto "centrale" è quello di ricavare la dimensione della lista, e poi scorrerla finchè non arrivo a metà, vero?
Io comunque adesso ho ancora un mare di esercizi da fare, ma alla prossima occasione ci riprovo con le liste visto che molto probabilmente ricapiterà un esercizio simile.

[apatriarca]

Affinché la successione di valori sia ordinata non è necessario che la suddivisione avvenga come normalmente spiegato prendendo la prima metà dei valori e poi la seconda. Per ordinare liste si usa una suddivisione alternativa dei valori. Si considerano infatti le due liste con indici rispettivamente positivi e negativi. Ti mostro un semplice esempio di lista di 7 valori:

lista: 3 5 2 1 7 4 6
Divido prima di tutto la lista nelle due sottoliste seguenti
S1: 3 2 7 6
S2: 5 1 4
A questo punto suppongo di applicare l'algoritmo ad entrambe le sottoliste ottenendo alla fine
S1 ordinata: 2 3 6 7
S2 ordinata: 1 4 5
Infine posso fare il merge come al solito ottenendo 1 2 3 4 5 6 7 come voluto.

L'unico svantaggio di questa versione è che l'algoritmo di ordinamento non è più stabile..

[Atem1]

Perchè non è stabile? Che problemi può dare?