El
ordenamiento de una lista simplemente enlazada es similar al
ordenamiento de vectores con
la gran diferencia de que en una lista simplemente enlazada no
disponemos del concepto del “índice” que nos ayuda a acceder
directamente a un elemento de la lista, en este caso para acceder a
un elemento debemos recorrer desde el inicio hasta hallar el elemento
que nos interese.
Un
algoritmo sencillo es el del Intercambio, consiste en lo siguiente:
1.
Situar un puntero al inicio de la lista que nos irá indicando a
medida que vayamos ordenando, cuánto de la lista ya está ordenada,
es la variable más importante del algoritmo porque nos servirá para
saber que hemos acabado de ordenar la lista.
Elemento
* elemBase = elemInicio;
while(elemBase
!= NULL)
{
//en
este proceso vamos ordenando la lista a partir del nodo elemBase
hasta el final
elemBase
= elemBase->next;
}
2.
En el caso que el ordenamiento sea de menor a mayor, necesitamos
encontrar el menor de los elementos a partir del elemento base hasta
el final de la lista.
En
el caso del ordenamiento de Vectores obteníamos la posición, en
este caso obtendremos un puntero al menor elemento.
Elemento*
buscarMenor(Elemento* ptrInicial)
Esta
función tendría que utilizarse en cada iteración
Elemento
* elemBase = elemInicio;
Elemento*
elemMenor; //puntero que nos sirve para apuntar al menor elemento
encontrado
while(elemBase
!= NULL)
{
elemMenor
= buscarMenor(elemBase);
elemBase
= elemBase->next;
}
3.
Intercambiar el elemento menor con el elemento que se encuentra
apuntando el puntero base. Para hacer este intercambio es necesario
que el elemento anterior al elemento base apunte al elemento menor,
para eso necesitamos un puntero que apunte al anterior del elemento
base.
Como
es una lista simplemente enlazada, no podemos retroceder para hallar
al puntero anterior al puntero base, por tanto, crearemos una función
que nos sirva para ubicarnos en el elemento anterior que queramos.
Esta función es necesaria para luego poder hacer el intercambio de
nodos.
Elemento
* getElemAnterior(Elemento* elemInicio, Elemento* elem);
Utilizaremos
esta función para obtener el elemento anterior al base y al menor y
de esta forma poder realizar el intercambio
Elemento
* elemAnteBase = NULL;//puntero que apunta al anterior de elemento
base
Elemento
* elemBase = elemInicio;
Elemento*
elemAnteMenor; //puntero que apunta al anterior del elemento menor
Elemento*
elemMenor; //puntero que nos sirve para apuntar al menor elemento
encontrado
while(elemBase
!= NULL)
{
elemMenor
= buscarMenor(elemBase);
elemAnteBase
= getElemAnterior(elemInicio, elemBase);
elemAnteMenor
= getElemAnterior(elemInicio, elemMenor);
elemBase
= elemBase->next;
}
Teniendo
el puntero anterior al base ya podemos hacer el intercambio:
void
intercambio(Elemento* elemAnteBase, Elemento* elemBase,
Elemento*
elemAnteMenor, Elemento* elemMenor);
Incorporamos
el intercambio en cada iteración y asignamos el nodo menor como el
nuevo elemento base:
Elemento
* elemAnteBase = NULL;//puntero que apunta al anterior de elemento
base
Elemento
* elemBase = elemInicio;
Elemento*
elemAnteMenor; //puntero que apunta al anterior del elemento menor
Elemento*
elemMenor; //puntero que nos sirve para apuntar al menor elemento
encontrado
while(elemBase
!= NULL)
{
elemMenor
= buscarMenor(elemBase);
elemAnteBase
= getElemAnterior(elemInicio, elemBase);
elemAnteMenor
= getElemAnterior(elemInicio, elemMenor);
intercambio(elemAnteBase,
elemBase, elemAnteMenor, elemMenor);
elemBase
= elemMenor;
elemBase
= elemBase->next;
}
4.
Finalmente desarrollamos las funciones:
Elemento*
buscarMenor(Elemento* ptrInicial)
{
Elemento*
elemMenor = ptrInicial;
Elemento*
ptr = ptrInicial;//puntero que sirve para recorrer la lista
int
menorValor = elemMenor.valor;//inicializamos el primer valor menor
//recorremos
toda la lista y dejamos el puntero elemMenor en el de menor valor
while(ptr!=NULL)
{
if(ptr.valor <
menorValor)
{
elemMenor = ptr;
menorValor =
ptr.valor;
}
ptr
= ptr->next;
}
return
elemMenor;
}
void
intercambio(Elemento* elemAnteBase, Elemento* elemBase,
Elemento*
elemAnteMenor, Elemento* elemMenor)
{
Elemento*
aux = elemBase->next; //nos sirve para hacer el intercambio sin
perder punteros
elemBase->next =
elemMenor->next;
elemMenor->next =
aux;
elemAnteBase->next
= elemMenor;
elemAnteMenor->next
= elemBase;
}
Elemento
* getElemAnterior(Elemento* elemInicio, Elemento* elem)
{
Elemento*anterior =
NULL;
Elemento*ptr
= elemInicio;
int
finBusqueda = 0;
while(ptr!=NULL &&
ptr->next!=NULL && !finBusqueda)
{
if(ptr->next.valor
== elem.valor)
{
finBusqueda = 1;
}
anterior
= ptr;
ptr
= ptr->next;
}
return
anterior;
}
