[C] Double Linked List - Puntatori a funzione - Algoritmi di ordinamento - Quick Sort

[Vincenzo1968]

Un amico, studente universitario, mi ha chiesto un algoritmo per l'ordinamento di una double linked list.
Nella speranza che possa essere utile a qualcuno, posto il codice.

Partiamo da una lista semplice (con solo il puntatore all'elemento successivo)

Codice :

#include <stdio.h>
#include <malloc.h>
#include <string.h>


int nMemoriaAllocata = 0;
int nMemoriaDeallocata = 0;


struct tagPersona
{
	int Anni;
	char Cognome[50];
	char Nome[50];
	struct tagPersona *next;
};


typedef struct tagPersona Persona;


int ConfrontaAnni(const Persona *p1, const Persona *p2)
{
	if ( p1->Anni < p2->Anni )
		return -1;
	else if ( p1->Anni > p2->Anni )
		return 1;
	else
		return 0;
}

/*
int ConfrontaCognome(const Persona *p1, const Persona *p2)
{
	return strcmp(p1->Cognome, p2->Cognome);
}
*/

int ConfrontaCognomeNome(const Persona *p1, const Persona *p2)
{
	char szCognomeNome1[100];
	char szCognomeNome2[100];

	strcpy(szCognomeNome1, p1->Cognome);
	strcat(szCognomeNome1, p1->Nome);

	strcpy(szCognomeNome2, p2->Cognome);
	strcat(szCognomeNome2, p2->Nome);

	return strcmp(szCognomeNome1, szCognomeNome2);
}


int (*Confronta)(const Persona *, const Persona *) = NULL;



Persona* Find(Persona *Pers, Persona *first)
{
	Persona *n = first;

	while( n != NULL )
	{
		if( (*Confronta)(n, Pers) == 0 )
			return n;
		n = n->next;
	}

	return NULL;
}

Persona *FindPrev(Persona *curr, Persona *first)
{
	for(; first && first->next; first = first->next)
	{
		if( curr == first->next )
		{
			break;
		}
	}
	
	if ( first->next != curr )
	{
		return curr;
	}
	
	return first;
}

Persona* Delete(Persona *Pers, Persona *first)
{
	Persona *n = first;

	n = Find(Pers, first);

	if( n == NULL )
		return first;

	// Cancellazione primo elemento
	if( n == first )
	{
		n = n->next;
		free(first);
		nMemoriaDeallocata += sizeof(Persona);
		return n;
	}

	// Prendiamo un puntatore all'elemento precedente;
	// ci servirà per cancellare l'elemento
	Persona *prevPers = NULL;
	n = first;

	while ( (*Confronta)(n, Pers) != 0 )
	{
		prevPers = n;
		n = n->next;
	}

	// Cancellazione ultimo elemento
	if ( n->next == NULL )
	{
		free(n);
		nMemoriaDeallocata += sizeof(Persona);
		prevPers->next = NULL;
		return first;
	}

	// Cancellazione elemento
	prevPers->next = n->next;
	free(n);
	nMemoriaDeallocata += sizeof(Persona);

	return first;
}

void Print(Persona *first)
{
	Persona *n = first;

	while( n != NULL )
	{
		printf("%d %s %s \n", n->Anni, n->Cognome, n->Nome);
		n = n->next;
	}
}

void Free(Persona *first)
{
	Persona *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		nMemoriaDeallocata += sizeof(Persona);
		n1 = n2;
	}
}

Persona* NewNode(Persona *Pers)
{
	Persona *n;

	n = (Persona *)malloc(sizeof(Persona));

	if( n == NULL )
		return NULL;

	n->Anni = Pers->Anni;
	strcpy(n->Cognome, Pers->Cognome);
	strcpy(n->Nome, Pers->Nome);
	n->next = NULL;

	nMemoriaAllocata += sizeof(Persona);

	return n;
}

Persona* Insert(Persona *Pers, Persona *first)
{
	Persona *n = first, *nuovo;

	// catena vuota
	if ( first == NULL )
		return NewNode(Pers);

	if( (*Confronta)(n, Pers) > 0 )
	{
		nuovo = NewNode(Pers);
		nuovo->next = first;
		return nuovo;
	}

	while( n != NULL)
	{
		if( (*Confronta)(n, Pers) == 0 )
		{
			return first;
		}
		n = n->next;
	}

	n = first;
	while( n->next != NULL )
	{
		if( (*Confronta)(n->next, Pers) > 0 )
		{
			nuovo = NewNode(Pers);
			nuovo->next = n->next;
			n->next = nuovo;
			return first;
		}
		n = n->next;
	}

	nuovo = NewNode(Pers);

	n->next = nuovo;

	return first;
}

tagPersona* Append(Persona *Pers, Persona *first)
{
	Persona *n = first, *nuovo;

	// catena vuota
	if ( first == NULL )
		return NewNode(Pers);

	n = first;
	while( n->next != NULL )
	{
		n = n->next;
	}

	nuovo = NewNode(Pers);
	n->next = nuovo;

	return first;
}


// Routines per l'ordinamento

Persona *SwapNodes(Persona *node1, Persona *node2, Persona *first)
{
	Persona *node1prev, *node2prev, *tmp;

	node1prev = FindPrev(node1, first);
	node2prev = FindPrev(node2, first);
	
	tmp = node2->next;

	// Se l'elementop è iol primo della lista
	if (node1 != first)
	{
		node1prev->next = node2;
	}
	else
	{
		first = node2;
	}
	
	// Sono due elementi adiacenti?
	if (node1->next == node2)
	{
		node2->next = node1;
		node1->next = tmp;
	}
	else
	{
		node2->next = node1->next;
		node1->next = tmp;
		node2prev->next = node1;
	}
	
	return first;
}

Persona *GetNthNode(int n, Persona *first)
{
	int i = 1;
	for( i = 1; i < n; i++ )
	{
		first = first->next;
	}
	
	return first;
}

int NumNodes(Persona *end, Persona *first)
{
	int i;

	for( i = 1; first && (first != end); i++)
	{
		first = first->next;
	}
	
	if (first != end)
	{
		return 0;
	}

	return i;
}

int countnodes(Persona *first)
{
	int i = 0;

	for (; first; first = first->next)
		i++;

	return i;
}

Persona *SelectPivot(Persona *first, Persona *end)
{
	Persona *right, *noden;
	int n;

	n = NumNodes(end, first);

	noden = GetNthNode((int)((float)n/2+0.5), first);
	right = FindPrev(end, first);

	if (noden != right)
	{
		SwapNodes(noden, right->next, first);
		return noden;
	}
	else
	{
		return noden->next;
	}
}

Persona * quicksort(Persona *first, int list_start, int list_end) 
{
	Persona *pivot, *left = first, *right = first, *tmp;
	int i = list_start, j = list_end - 1;

	if (list_start >= list_end)
	{
		return first;
	}

	right = GetNthNode(list_end, first);
	left = GetNthNode(list_start, first);

	pivot = SelectPivot(left, right);

	right = FindPrev(pivot, left);

	for(;;)
	{
		for(; ( (*Confronta)(left, pivot) < 0 ); left=left->next, i++);

		for(; ( (*Confronta)(right, pivot) > 0 ) ; right = FindPrev(right, first), j--);

		if (i < j)
		{
			first = SwapNodes(left, right, first);
			tmp = left;
			left = right;
			right = tmp;
		}
		else
			break;
	}

	// Ripristina il pivot
	first = SwapNodes(left, pivot, first); 

	first = quicksort(first, list_start, i-1);
	first = quicksort(first, i+1, list_end);

	return first;
}

// Wrapper per la funzione 'quicksort'
Persona *QSort(Persona *first)
{
	int n;
  
	n = countnodes(first);

	// Chiama la funzione 'quicksort'
	// Numeriamo gli elementi da 1 a n
	// invece che da 0 a n-1
	return quicksort(first, 1, n);
}


int main(int argc, char* argv[])
{
	Confronta = ConfrontaCognomeNome;

	int i, N;

	Persona Pers;
	Persona *pPers = NULL;

	N = 5;

	Pers.Anni = 45;
	strcpy(Pers.Cognome, "Sciascia");
	strcpy(Pers.Nome, "Leonardo");

	//pPers = Insert(&Pers, pPers);
	pPers = Append(&Pers, pPers);

	for ( i = 2; i <= N; i++ )
	{
		if ( i == 2 )
		{
			Pers.Anni = 70;
			strcpy(Pers.Cognome, "Camilleri");
			strcpy(Pers.Nome, "Andrea");
		}
		else if ( i == 3 )
		{
			Pers.Anni = 54;
			strcpy(Pers.Cognome, "Orwell");
			strcpy(Pers.Nome, "George");
		}
		else if ( i == 4 )
		{
			Pers.Anni = 65;
			strcpy(Pers.Cognome, "Pirandello");
			strcpy(Pers.Nome, "Luigi");
		}
		else if ( i == 5 )
		{
			Pers.Anni = 68;
			strcpy(Pers.Cognome, "Simenon");
			strcpy(Pers.Nome, "Georges");
		}

		//pPers = Insert(&Pers, pPers);
		pPers = Append(&Pers, pPers);
	}

	printf("\nLista non ordinata:\n");
	Print(pPers);

	//Pers.Anni = 54;
	//strcpy(Pers.Cognome, "Orwell");
	//strcpy(Pers.Nome, "George");
	//pPers = Delete(&Pers, pPers);

	pPers = QSort(pPers);

	printf("\nLista Ordinata:\n");
	Print(pPers);

	Free(pPers);

	printf("\nTotale Memoria Allocata: %d\nTotale Memoria Deallocata: %d\n", nMemoriaAllocata, nMemoriaDeallocata);

	return 0;
}

Per l'ordinamento utilizziamo l'algoritmo chaiamato 'Quick Sort' del mitico C.A.R. Hoare, che è generalmente considerato il
migliore (ma, nel caso di una lista con pochi elementi, come nell'esempio proposto, risultati migliori, dal punto di vista
della velocità di esecuzione, si potrebbero ottenere persino con un algoritmo poco efficiente come il 'Bubble Sort').

per confrontare due elementi, utilizziamo un puntatore a una funzione definita dall'utente:

int (*Confronta)(const Persona *, const Persona *) = NULL;

La sintassi dei puntatori a funzione è leggermente complicata ma ci permette di ordinare la lista in base a diversi parametri.
Per esempio, se invece che per Cognome + Nome, vogliamo un lista ordinata per Anni, tutto quello che dobbiamo fare, nel 'main',
è cambiare il puntatore alla funzione di confronto, da

	Confronta = ConfrontaCognomeNome;

a

	Confronta = ConfrontaAnni;

C'è da dire, infine, che il metodo migliore in assoluto, per avere una lista ordinata, è quello di ordinare gli elementi mentre
li andiamo inserendo.

È quello cha fa la funzione "Insert". Per utilizzarla, sostituiamola, nel 'main' allla chiamata alla funzione 'Append'
(e togliamo anche la chiamata alla funzione 'QSort') :

int main(int argc, char* argv[])
{
	Confronta = ConfrontaCognomeNome;

	int i, N;

	Persona Pers;
	Persona *pPers = NULL;

	N = 5;

	Pers.Anni = 45;
	strcpy(Pers.Cognome, "Sciascia");
	strcpy(Pers.Nome, "Leonardo");

	pPers = Insert(&Pers, pPers);

	for ( i = 2; i <= N; i++ )
	{
		if ( i == 2 )
		{
			Pers.Anni = 70;
			strcpy(Pers.Cognome, "Camilleri");
			strcpy(Pers.Nome, "Andrea");
		}
		else if ( i == 3 )
		{
			Pers.Anni = 54;
			strcpy(Pers.Cognome, "Orwell");
			strcpy(Pers.Nome, "George");
		}
		else if ( i == 4 )
		{
			Pers.Anni = 65;
			strcpy(Pers.Cognome, "Pirandello");
			strcpy(Pers.Nome, "Luigi");
		}
		else if ( i == 5 )
		{
			Pers.Anni = 68;
			strcpy(Pers.Cognome, "Simenon");
			strcpy(Pers.Nome, "Georges");
		}

		pPers = Insert(&Pers, pPers);
	}

	printf("\nLista non ordinata:\n");
	Print(pPers);

	printf("\nLista Ordinata:\n");
	Print(pPers);

	Free(pPers);

	printf("\nTotale Memoria Allocata: %d\nTotale Memoria Deallocata: %d\n", nMemoriaAllocata, nMemoriaDeallocata);

	return 0;
}

[Vincenzo1968]

Questo invece è il codice per le double linked list :

#include <stdio.h>
#include <malloc.h>
#include <string.h>


int nMemoriaAllocata = 0;
int nMemoriaDeallocata = 0;


struct tagPersona
{
	int Anni;
	char Cognome[50];
	char Nome[50];
	struct tagPersona *prev;
	struct tagPersona *next;
};

typedef struct tagPersona Persona;

int ConfrontaAnni(const Persona *p1, const Persona *p2)
{
	if ( p1->Anni < p2->Anni )
		return -1;
	else if ( p1->Anni > p2->Anni )
		return 1;
	else
		return 0;
}

/*
int ConfrontaCognome(const Persona *p1, const Persona *p2)
{
	return strcmp(p1->Cognome, p2->Cognome);
}
*/

int ConfrontaCognomeNome(const Persona *p1, const Persona *p2)
{
	char szCognomeNome1[100];
	char szCognomeNome2[100];

	strcpy(szCognomeNome1, p1->Cognome);
	strcat(szCognomeNome1, p1->Nome);

	strcpy(szCognomeNome2, p2->Cognome);
	strcat(szCognomeNome2, p2->Nome);

	return strcmp(szCognomeNome1, szCognomeNome2);
}


int (*Confronta)(const Persona *, const Persona *) = NULL;



// Routines per la gestione ordinaria della lista

Persona* NewNode(Persona *Pers)
{
	Persona *n;

	n = (Persona *)malloc(sizeof(Persona));

	if( n == NULL )
		return NULL;

	n->Anni = Pers->Anni;
	strcpy(n->Cognome, Pers->Cognome);
	strcpy(n->Nome, Pers->Nome);
	n->prev = NULL;
	n->next = NULL;

	nMemoriaAllocata += sizeof(Persona);

	return n;
}

Persona* Insert(Persona *Pers, Persona *first)
{
	Persona *n = first, *nuovo;

	int more = 1;

	// catena vuota
	if ( first == NULL )
		return NewNode(Pers);

	if( (*Confronta)(n, Pers) > 0 )
	{
		nuovo = NewNode(Pers);
		nuovo->next = first;
		first->prev = nuovo;
		return nuovo;
	}

	while( n != NULL)
	{
		if( (*Confronta)(n, Pers) == 0 )
		{
			return first;
		}
		n = n->next;
	}

	n = first;
	while( n->next != NULL )
	{
		if( (*Confronta)(n->next, Pers) > 0 )
		{
			nuovo = NewNode(Pers);
			n->next->prev = nuovo;
			nuovo->next = n->next;
			nuovo->prev = n;
			n->next = nuovo;
			return first;
		}
		n = n->next;
	}

	nuovo = NewNode(Pers);

	n->next = nuovo;

	nuovo->prev = n;

	return first;
}

Persona* Append(Persona *Pers, Persona *first)
{
	Persona *n = first, *nuovo;

	int more = 1;

	// catena vuota
	if ( first == NULL )
		return NewNode(Pers);

	n = first;
	while( n->next != NULL )
	{
		n = n->next;
	}

	nuovo = NewNode(Pers);

	n->next = nuovo;

	nuovo->prev = n;

	return first;
}

Persona* Find(Persona *Pers, Persona *first)
{
	Persona *n = first;

	while( n != NULL )
	{
		if( (*Confronta)(n, Pers) == 0 )
			return n;

		n = n->next;
	}

	return NULL;
}

Persona* Delete(Persona *Pers, Persona *first)
{
	Persona *n = first;

	n = Find(Pers, first);

	if( n == NULL )
		return first;

	if( n->next != NULL )
		n->next->prev = n->prev;

	if( n->prev != NULL )
		n->prev->next = n->next;

	if( n == first )
	{
		n = n->next;
		free(first);
		nMemoriaDeallocata += sizeof(struct tagPersona);
		return n;
	}

	free(n);
	nMemoriaDeallocata += sizeof(Persona);

	return first;
}

void Print(Persona *first)
{
	Persona *n = first;

	Persona *z;

	while( n != NULL )
	{
		printf("%d %s %s \n", n->Anni, n->Cognome, n->Nome);
		n = n->next;
		if ( n != NULL )
			z = n;
	}

	printf("\nStampa in ordine decrescente:\n\n");

	while ( z != NULL )
	{
		printf("%d %s %s \n", z->Anni, z->Cognome, z->Nome);
		z = z->prev;	
	}
}

void Free(Persona *first)
{
	Persona *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		nMemoriaDeallocata += sizeof(Persona);
		n1 = n2;
	}
}


// Routines per l'ordinamento

Persona *SwapNodes(Persona *node1, Persona *node2, Persona *first)
{
	Persona *node1prev, *node2prev, *tmp, *tmp2;

	node1prev = node1->prev;
	node2prev = node2->prev;

	tmp = node2->next;

	tmp2 = node1->next;

	if (node1 != first)
	{
		node1prev->next = node2;
	}
	else
	{
		first = node2;
	}

	// Sono due nodi adiacenti?
	if (node1->next == node2) 
	{
		// I nodi sono adiacenti
		
		node2->next = node1;
		node1->next = tmp;

		node2->prev = node1prev;
		node1->prev = node2;
		
		if ( node1->next )
			tmp->prev = node1;
	}
	else 
	{
		// I nodi non sono adiacenti

		node2->next = node1->next;
		node1->next = tmp;
		
		node2->prev = node1prev;
		node1->prev = node2prev;
		
		node2prev->next = node1;
		node2prev->prev = tmp2;
		
		if ( node1->next )
			tmp->prev = node1;
		
		tmp2->prev = node2;
	}
	
	return first;
}

Persona *GetNthNode(int n, Persona *first)
{
	int i = 1;

	for( i = 1; i < n; i++)
	{
		first = first->next;
	}
	
	return first;
}

int NumNodes(Persona *first, Persona *end)
{
	int i;
	
	for( i = 1; first && ( first != end );i++)
	{
		first = first->next;
	}
	
	if (first != end)
	{
		return 0;
	}
	
	return i;
}

int countnodes(Persona *first)
{
	int i = 0;

	for (;first; first = first->next)
		i++;
	
	return i;
}

Persona *SelectPivot(Persona *first, Persona *end)
{
	Persona *right, *noden;
	int n;

	n = NumNodes(first, end);

	noden = GetNthNode((int)((float)n/2+0.5), first);
	right = end->prev;
	if ( right == NULL )
		right = end;

	if (noden != right)
	{
		SwapNodes(noden, right->next, first);
		return noden;
	}
	else
	{
		return noden->next;
	}
}

Persona * quicksort(Persona *first, int list_start, int list_end) 
{
	Persona *pivot, *left = first, *right = first, *tmp;
	int i = list_start, j= list_end-1;

	if (list_start >= list_end)
	{
		return first;
	}

	right = GetNthNode(list_end, first);
	left = GetNthNode(list_start, first);

	pivot = SelectPivot(left, right);

	right = pivot->prev;
	if ( right == NULL )
		right = pivot;
	
	for(;;)
	{
		for(; ( (*Confronta)(left, pivot) < 0 ); left = left->next, i++);
		
		for(; ( (*Confronta)(right, pivot) > 0 ); right = right->prev, j--);
		
		if (i < j)
		{
			first = SwapNodes(left, right, first);
			tmp = left;
			left = right;
			right = tmp;
		}
		else
			break;
	}
	
	// Ripristina il pivot
	first = SwapNodes(left, pivot, first); 
	
	first = quicksort(first, list_start, i-1);
	first = quicksort(first, i+1, list_end);

	return first;
}

// Wrapper per la funzione 'quicksort'
Persona *QSort(Persona *first)
{
	int n;
	
	n = countnodes(first);

	// Chiama la funzione 'quicksort'
	// Numeriamo gli elementi da 1 a n
	// invece che da 0 a n-1
	return quicksort(first, 1, n);
}



int main(int argc, char* argv[])
{
	Confronta = ConfrontaCognomeNome;

	int i, N;

	Persona Pers;
	Persona *pPers = NULL;

	N = 5;

	Pers.Anni = 45;
	strcpy(Pers.Cognome, "Sciascia");
	strcpy(Pers.Nome, "Leonardo");
	//pPers = Insert(&Pers, pPers);
	pPers = Append(&Pers, pPers);


	for ( i = 2; i <= N; i++ )
	{
		if ( i == 2 )
		{
			Pers.Anni = 70;
			strcpy(Pers.Cognome, "Camilleri");
			strcpy(Pers.Nome, "Andrea");
		}
		else if ( i == 3 )
		{
			Pers.Anni = 54;
			strcpy(Pers.Cognome, "Orwell");
			strcpy(Pers.Nome, "George");
		}
		else if ( i == 4 )
		{
			Pers.Anni = 65;
			strcpy(Pers.Cognome, "Pirandello");
			strcpy(Pers.Nome, "Luigi");
		}
		else if ( i == 5 )
		{
			Pers.Anni = 68;
			strcpy(Pers.Cognome, "Simenon");
			strcpy(Pers.Nome, "Georges");
		}

		//pPers = Insert(&Pers, pPers);
		pPers = Append(&Pers, pPers);
	}

	printf("\nLista non ordinata:\n\n");
	Print(pPers);

	//Pers.Anni = 54;
	//strcpy(Pers.Cognome, "Orwell");
	//strcpy(Pers.Nome, "George");
	//pPers = Delete(&Pers, pPers);

	pPers = QSort(pPers);

	printf("\nLista Ordinata:\n\n");
	Print(pPers);

	Free(pPers);

	printf("\nTotale Memoria Allocata: %d\nTotale Memoria Deallocata: %d\n", nMemoriaAllocata, nMemoriaDeallocata);

	return 0;
}

[Vincenzo1968]

C'è un bug nella funzione SwapNode.

Per eliminarlo bisogna aggiungere la seguente istruzione in cima alla funzione ( sia nella versione 'Simple List' che in 'Double List' ) :

if ( node1 == node2 )
	return first;

Questo è il codice completo della funzione per la versione 'Simple List' :

Persona *SwapNodes(Persona *node1, Persona *node2, Persona *first)
{

    if ( node1 == node2 )
	return first;

    Persona *node1prev, *node2prev, *tmp;

    node1prev = FindPrev(node1, first);
    node2prev = FindPrev(node2, first);
	
    tmp = node2->next;

    // Se l'elementop è iol primo della lista
    if (node1 != first)
    {
	node1prev->next = node2;
    }
    else
    {
	first = node2;
    }
	
    // Sono due elementi adiacenti?
    if (node1->next == node2)
    {
	node2->next = node1;
	node1->next = tmp;
    }
    else
    {
	node2->next = node1->next;
	node1->next = tmp;
	node2prev->next = node1;
    }
	
    return first;
}

e questo è quello per la versione 'Double List' :

Persona *SwapNodes(Persona *node1, Persona *node2, Persona *first)
{
    if ( node1 == node2 )
	return first;

    Persona *node1prev, *node2prev, *tmp, *tmp2;

    node1prev = node1->prev;
    node2prev = node2->prev;

    tmp = node2->next;

    tmp2 = node1->next;

    if (node1 != first)
    {
	node1prev->next = node2;
    }
    else
    {
	first = node2;
    }

    // Sono due nodi adiacenti?
    if (node1->next == node2) 
    {
	// I nodi sono adiacenti
		
	node2->next = node1;
	node1->next = tmp;

	node2->prev = node1prev;
	node1->prev = node2;
		
	if ( node1->next )
		tmp->prev = node1;
    } 
    else 
    {
	// I nodi non sono adiacenti
	node2->next = node1->next;
	node1->next = tmp;
		
	node2->prev = node1prev;
	node1->prev = node2prev;
		
	node2prev->next = node1;
	node2prev->prev = tmp2;
		
	if ( node1->next )
		tmp->prev = node1;
		
	tmp2->prev = node2;
    }
	
    return first;
}

[Vincenzo1968]

Questa è la versione iterativa ( non ricorsiva ) del QuickSort per le liste :

Linked List :

Persona * QuickSortNonRecursive(Persona *first, int list_start, int list_end) 
{
Persona *pivot, *left = first, *right = first, *tmp;
int i, j;
int s = 0;

int stack[64];

if (list_end <= list_start)
	return first;

stack[s++] = list_start;
stack[s++] = list_end;

while ( s > 0 )
{
	list_end = stack[--s];
	list_start = stack[--s];

	if ( list_start >= list_end )
		continue;

	// INIZIO PARTIZIONAMENTO

	i = list_start;
	j = list_end - 1;

	right = GetNthNode(list_end, first);
	left = GetNthNode(list_start, first);
	pivot = SelectPivot(left, right);
	right = FindPrev(pivot, left);

	for(;;)
	{
		for(; ((*Confronta)(left, pivot) < 0); left = left->next, i++);

		for(; ((*Confronta)(right, pivot) > 0) ; right = FindPrev(right, first), j--);

		if ( i >= j )
			break;
	
		first = SwapNodes(left, right, first);
		tmp = left;
		left = right;
		right = tmp;
	}

	// Ripristina il pivot
	first = SwapNodes(left, pivot, first); 

	// FINE PARTIZIONAMENTO

	if (i - list_start > list_end - i)
	{
		stack[s++] = list_start;
		stack[s++] = i - 1;
		stack[s++] = i + 1;
		stack[s++] = list_end;
	}
	else
	{
		stack[s++] = i + 1;
		stack[s++] = list_end;
		stack[s++] = list_start;
		stack[s++] = i - 1;
	}
}

return first;
}

Double Linked List :

Persona * QuickSortNonRecursive(Persona *first, int list_start, int list_end) 
{
Persona *pivot, *left = first, *right = first, *tmp;
int i, j;
int s = 0;

int stack[64];

if (list_end <= list_start)
	return first;

stack[s++] = list_start;
stack[s++] = list_end;

while ( s > 0 )
{
	list_end = stack[--s];
	list_start = stack[--s];

	if ( list_start >= list_end )
		continue;

	// INIZIO PARTIZIONAMENTO

	i = list_start;
	j = list_end - 1;

	right = GetNthNode(list_end, first);
	left = GetNthNode(list_start, first);
	pivot = SelectPivot(left, right);
	right = pivot->prev;

	for(;;)
	{
		for(; ( (*Confronta)(left, pivot) < 0 ); left = left->next, i++);

		for(; ( (*Confronta)(right, pivot) > 0 ) ; right = right->prev, j--);

		if ( i >= j )
			break;
	
		first = SwapNodes(left, right, first);
		tmp = left;
		left = right;
		right = tmp;
	}

	// Ripristina il pivot
	first = SwapNodes(left, pivot, first); 

	// FINE PARTIZIONAMENTO

	if (i - list_start > list_end - i)
	{
		stack[s++] = list_start;
		stack[s++] = i - 1;
		stack[s++] = i + 1;
		stack[s++] = list_end;
	}
	else
	{
		stack[s++] = i + 1;
		stack[s++] = list_end;
		stack[s++] = list_start;
		stack[s++] = i - 1;
	}
}

return first;
}

nella funzione 'QSort', sostituiamo la chiamata a 'quicksort' con 'QuickSortNonRecursive' :

// Wrapper per la funzione 'quicksort'
Persona *QSort(Persona *first)
{
	int n;
  
	n = countnodes(first);

	// Chiama la funzione 'quicksort'
	// Numeriamo gli elementi da 1 a n
	// invece che da 0 a n-1

	//return quicksort(first, 1, n);

	return QuickSortNonRecursive(first, 1, n);
}

[Vincenzo1968]

C'è, nel codice precedente, un bug per quanto riguarda le liste doppiamente concatenate.
Posto il codice corretto (almeno spero: l'ho testato più volte).
Se riscontrate qualche bug, per favore, fatemelo sapere.

Dopo tanto lavoro, alla fine credo ne sia valsa la pena. Facendo una ricerca su google, non sono riuscito a trovare un
solo esempio di codice per il QuickSort applicato alla Double linked list (e figuriamoci con tutt'e due i metodi : ricorsivo e iterativo).

Double linked list

#include <stdio.h>
#include <malloc.h>
#include <string.h>

int nMemoriaAllocata = 0;
int nMemoriaDeallocata = 0;


struct tagPersona
{
	int Anni;
	char Cognome[50];
	char Nome[50];
	struct tagPersona *prev;
	struct tagPersona *next;
};

typedef struct tagPersona Persona;

int ConfrontaAnni(const Persona *p1, const Persona *p2)
{
	if ( p1->Anni < p2->Anni )
		return -1;
	else if ( p1->Anni > p2->Anni )
		return 1;
	else
		return 0;
}


/*
int ConfrontaCognome(const Persona *p1, const Persona *p2)
{
	return strcmp(p1->Cognome, p2->Cognome);
}
*/

int ConfrontaCognomeNome(const Persona *p1, const Persona *p2)
{
	char szCognomeNome1[100];
	char szCognomeNome2[100];

	strcpy(szCognomeNome1, p1->Cognome);
	strcat(szCognomeNome1, p1->Nome);

	strcpy(szCognomeNome2, p2->Cognome);
	strcat(szCognomeNome2, p2->Nome);

	return strcmp(szCognomeNome1, szCognomeNome2);
}

int (*Confronta)(const Persona *, const Persona *) = NULL;

// Routines per la gestione ordinaria della lista

Persona* NewNode(Persona *Pers)
{
	Persona *n;

	n = (Persona *)malloc(sizeof(Persona));

	if( n == NULL )
		return NULL;

	n->Anni = Pers->Anni;
	strcpy(n->Cognome, Pers->Cognome);
	strcpy(n->Nome, Pers->Nome);
	n->prev = NULL;
	n->next = NULL;

	nMemoriaAllocata += sizeof(Persona);

	return n;
}

Persona* Insert(Persona *Pers, Persona *first)
{
	Persona *n = first, *nuovo;

	int more = 1;

	// catena vuota
	if ( first == NULL )
		return NewNode(Pers);

	if( (*Confronta)(n, Pers) > 0 )
	{
		nuovo = NewNode(Pers);
		nuovo->next = first;
		first->prev = nuovo;
		return nuovo;
	}

	while( n != NULL)
	{
		if( (*Confronta)(n, Pers) == 0 )
		{
			return first;
		}
		n = n->next;
	}

	n = first;
	while( n->next != NULL )
	{
		if( (*Confronta)(n->next, Pers) > 0 )
		{
			nuovo = NewNode(Pers);
			n->next->prev = nuovo;
			nuovo->next = n->next;
			nuovo->prev = n;
			n->next = nuovo;
			return first;
		}
		n = n->next;
	}

	nuovo = NewNode(Pers);

	n->next = nuovo;

	nuovo->prev = n;

	return first;
}

Persona* Append(Persona *Pers, Persona *first)
{
	Persona *n = first, *nuovo;

	int more = 1;

	// catena vuota
	if ( first == NULL )
		return NewNode(Pers);

	n = first;
	while( n->next != NULL )
	{
		n = n->next;
	}

	nuovo = NewNode(Pers);

	n->next = nuovo;

	nuovo->prev = n;

	return first;
}

Persona* Find(Persona *Pers, Persona *first)
{
	Persona *n = first;

	while( n != NULL )
	{
		if( (*Confronta)(n, Pers) == 0 )
			return n;

		n = n->next;
	}

	return NULL;
}

Persona* Delete(Persona *Pers, Persona *first)
{
	Persona *n = first;

	n = Find(Pers, first);

	if( n == NULL )
		return first;

	if( n->next != NULL )
		n->next->prev = n->prev;

	if( n->prev != NULL )
		n->prev->next = n->next;

	if( n == first )
	{
		n = n->next;
		free(first);
		nMemoriaDeallocata += sizeof(struct tagPersona);
		return n;
	}

	free(n);
	nMemoriaDeallocata += sizeof(Persona);

	return first;
}

void Print(Persona *first)
{
	Persona *n = first;

	Persona *z;

	while( n != NULL )
	{
		printf("%d %s %s\n", n->Anni, n->Cognome, n->Nome);
		n = n->next;
		if ( n != NULL )
			z = n;
	}
	printf("\n");

	printf("Stampa in ordine decrescente:\n");

	//x = 0;
	while ( z != NULL )
	{
		printf("%d %s %s\n", z->Anni, z->Cognome, z->Nome);
		z = z->prev;	
	}
	printf("\n\n");
}

void Free(Persona *first)
{
	Persona *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		nMemoriaDeallocata += sizeof(Persona);
		n1 = n2;
	}
}


// Routines per l'ordinamento

Persona *SwapNodes(Persona *node1, Persona *node2, Persona *first)
{
	if ( node1 == node2 )
		return first;

	Persona *node1prev, *node2prev, *node1next, *node2next;

	Persona * tmp;

	node1prev = node1->prev;
	node2prev = node2->prev;

	node1next = node1->next;
	node2next = node2->next;

	if (node1 != first)
	{
		node1prev->next = node2;
		node1next->prev = node2;
	}
	else
	{
		node1next->prev = node2;
		first = node2;
	}

	if ( node1->next != node2 )
	{
		node2prev->next = node1;
		if ( node2next )
			node2next->prev = node1;

		tmp = node1;
		node1 = node2;
		node2 = tmp;

		node1->prev = node1prev;
		node1->next = node1next;

		node2->prev = node2prev;
		node2->next = node2next;
	}
	else
	{
		tmp = node2->next;
		node2->next = node1;
		node1->next = tmp;

		node2->prev = node1prev;
		node1->prev = node2;

		if ( node2next )
			node2next->prev = node1->prev->next;
	}
	
	return first;
}

Persona *GetNthNode(int n, Persona *first)
{
	int i = 1;

	for( i = 1; i < n; i++)
	{
		first = first->next;
	}
	
	return first;
}

int NumNodes(Persona *first, Persona *end)
{
	int i;
	
	for( i = 1; first && ( first != end );i++)
	{
		first = first->next;
	}
	
	if (first != end)
	{
		return 0;
	}
	
	return i;
}

int countnodes(Persona *first)
{
	int i = 0;

	for (;first; first = first->next)
		i++;
	
	return i;
}

Persona *SelectPivot(Persona *first, Persona *end)
{
	Persona *right, *noden;
	int n;

	n = NumNodes(first, end);

	noden = GetNthNode((int)((float)n/2+0.5), first);
	right = end->prev;

	if (noden != right)
	{
		SwapNodes(noden, right->next, first);
		return noden;
	}
	else
	{
		return noden->next;
	}
}

Persona * QuickSortNonRecursive(Persona *first, int list_start, int list_end) 
{
	Persona *pivot, *left = first, *right = first, *tmp;
	int i, j;
	int s = 0;

	int stack[64];

	if (list_end <= list_start)
		return first;

	stack[s++] = list_start;
	stack[s++] = list_end;

	while ( s > 0 )
	{
		list_end = stack[--s];
		list_start = stack[--s];

		if ( list_start >= list_end )
			continue;

		// INIZIO PARTIZIONAMENTO

		i = list_start;
		j = list_end - 1;

		right = GetNthNode(list_end, first);
		left = GetNthNode(list_start, first);
		pivot = SelectPivot(left, right);
		right = pivot->prev;

		for(;;)
		{
			for(;((*Confronta)(left, pivot)<0);left=left->next, i++);

			for(;((*Confronta)(right, pivot)>0) && (i< j);right=right->prev,j--);

			if ( i >= j )
				break;
	
			first = SwapNodes(left, right, first);
			tmp = left;
			left = right;
			right = tmp;
		}

		// Ripristina il pivot
		first = SwapNodes(left, pivot, first); 

		// FINE PARTIZIONAMENTO

		if (i - list_start > list_end - i)
		{
			stack[s++] = list_start;
			stack[s++] = i - 1;
			stack[s++] = i + 1;
			stack[s++] = list_end;
		}
		else
		{
			stack[s++] = i + 1;
			stack[s++] = list_end;
			stack[s++] = list_start;
			stack[s++] = i - 1;
		}
	}

	return first;
}

Persona * quicksort(Persona *first, int list_start, int list_end) 
{
	Persona *pivot, *left = first, *right = first, *tmp;
	int i = list_start, j = list_end - 1;

	if (list_start >= list_end)
	{
		return first;
	}

	right = GetNthNode(list_end, first);
	left = GetNthNode(list_start, first);
	pivot = SelectPivot(left, right);
	right = pivot->prev;

	tmp = NULL;

	for(;;)
	{
		for(;((*Confronta)(left,pivot) < 0 ; left=left->next,i++);

		for(;((*Confronta)(right,pivot) > 0) && (i < j); right=right->prev,j--);

		if (i < j)
		{
			first = SwapNodes(left, right, first);

			tmp = left;
			left = right;
			right = tmp;
		}
		else
			break;
	}

	// Ripristina il pivot
	first = SwapNodes(left, pivot, first); 
	
	first = quicksort(first, list_start, i-1);
	first = quicksort(first, i+1, list_end);

	return first;
}

// Wrapper per la funzione 'quicksort'
Persona *QSort(Persona *first)
{
	int n;
	
	n = countnodes(first);

	// Chiama la funzione 'quicksort'
	// Numeriamo gli elementi da 1 a n
	// invece che da 0 a n-1

	//return quicksort(first, 1, n);

	return QuickSortNonRecursive(first, 1, n);
}

int main(int argc, char* argv[])
{
	Confronta = ConfrontaCognomeNome;
	//Confronta = ConfrontaAnni;

	int i, N;

	Persona Pers;
	Persona *pPers = NULL;

	N = 5;

	/*
	for ( i = 1000; i > 0; i-- )
	{
		Pers.Anni = i;
		strcpy(Pers.Cognome, "A");
		strcpy(Pers.Nome, "B");

		pPers = Append(&Pers, pPers);
	}
	*/

	Pers.Anni = 45;
	strcpy(Pers.Cognome, "Sciascia");
	strcpy(Pers.Nome, "Leonardo");
	//pPers = Insert(&Pers, pPers);
	pPers = Append(&Pers, pPers);

	for ( i = 2; i <= N; i++ )
	{
		if ( i == 2 )
		{
			Pers.Anni = 70;
			strcpy(Pers.Cognome, "Camilleri");
			strcpy(Pers.Nome, "Andrea");
		}
		else if ( i == 3 )
		{
			Pers.Anni = 54;
			strcpy(Pers.Cognome, "Orwell");
			strcpy(Pers.Nome, "George");
		}
		else if ( i == 4 )
		{
			Pers.Anni = 65;
			strcpy(Pers.Cognome, "Pirandello");
			strcpy(Pers.Nome, "Luigi");
		}
		else if ( i == 5 )
		{
			Pers.Anni = 68;
			strcpy(Pers.Cognome, "Simenon");
			strcpy(Pers.Nome, "Georges");
		}

		//pPers = Insert(&Pers, pPers);
		pPers = Append(&Pers, pPers);
	}

	printf("\nLista non ordinata:\n\n");
	Print(pPers);

	//Pers.Anni = 54;
	//strcpy(Pers.Cognome, "Orwell");
	//strcpy(Pers.Nome, "George");
	//pPers = Delete(&Pers, pPers);
	
	pPers = QSort(pPers);

	printf("\nLista Ordinata:\n\n");
	Print(pPers);

	Free(pPers);

	printf("\nTotale memoria allocata:   %d\n", nMemoriaAllocata);
	printf("\nTotale memoria deallocata: %d\n", nMemoriaDeallocata);

	return 0;
}

[alka]

Interessante, ma le discussioni si aprono per porre domande e cercare risposte, non per proporre soluzioni non richieste (altrimenti chiunque potrebbe aprire un thread e scrivere ciò che preferisce, senza un contesto di riferimento ben preciso).