Ordenamiento de una lista simplemente enlazada

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;

}