codice:
void NaturalMergeSort(Posizione p) {
Lista<T> lista = EstraiLista(p);
TagliaLista(p);
Lista<T> A;
Lista<T> B;
do
{
A.AnnullaLista();
B.AnnullaLista();
Distribuisci(lista,A,B);
lista.AnnullaLista();
}while(Merge(lista, A, B) > 1);
*this += lista;
}
void Distribuisci(Lista<T> lista, Lista<T> &A, Lista<T> &B)
{
NodoLista<T>* nodoLista = lista.PrimoElemento();
NodoLista<T>* nodoA = A.PrimoElemento();
NodoLista<T>* nodoB = B.PrimoElemento();
do
{
CopiaCatena(lista,nodoLista,A,nodoA);
if(!lista.FineLista(nodoLista))
CopiaCatena(lista,nodoLista,B,nodoB);
}while(!lista.FineLista(nodoLista)); // Qui si trova la causa di tutto
}
void CopiaCatena(Lista<T> listaOrigine, NodoLista<T>*& nodoOrigine, Lista<T>& lista, NodoLista<T>*& nodoLista)
{
while(!Copia(listaOrigine,nodoOrigine,lista,nodoLista));
}
bool Copia(Lista<T> listaOrigine, NodoLista<T>*& nodoOrigine, Lista<T>& lista, NodoLista<T>*& nodoLista)
{
T Elemento = listaOrigine[nodoOrigine];
lista.Inserisci(&nodoLista,Elemento);
nodoLista = lista.Next(nodoLista);
nodoOrigine = listaOrigine.Next(nodoOrigine);
if(listaOrigine.FineLista(nodoOrigine))
return true;
else
return (Elemento > listaOrigine.Leggi(nodoOrigine));
}
int Merge(Lista<T>& listaRisultato, Lista<T> listaA, Lista<T> listaB)
{
NodoLista<T>* nodoLista = listaRisultato.PrimoElemento();
NodoLista<T>* nodoA = listaA.PrimoElemento();
NodoLista<T>* nodoB = listaB.PrimoElemento();
int NumeroCatene = 0;
while(!listaA.FineLista(nodoA) && !listaB.FineLista(nodoB))
{
FondiCatena(listaRisultato,nodoLista,listaA,nodoA,listaB,nodoB);
NumeroCatene++;
}
while(!listaA.FineLista(nodoA))
{
CopiaCatena(listaA,nodoA,listaRisultato,nodoLista);
NumeroCatene++;
}
while(!listaB.FineLista(nodoB))
{
CopiaCatena(listaB,nodoB,listaRisultato,nodoLista);
NumeroCatene++;
}
return NumeroCatene;
}
void FondiCatena(Lista<T>& listaR,NodoLista<T>*& nodoR,Lista<T> A, NodoLista<T>*& nodoA,Lista<T> B, NodoLista<T>*& nodoB)
{
bool FineCatena;
do
{
if(A.Leggi(nodoA) < B.Leggi(nodoB))
{
FineCatena = Copia(A,nodoA,listaR,nodoR);
if(FineCatena)
CopiaCatena(B,nodoB,listaR,nodoR);
}
else
{
FineCatena = Copia(B,nodoB,listaR,nodoR);
if(FineCatena)
CopiaCatena(A,nodoA,listaR,nodoR);
}
}while(!FineCatena);
}
};