Ordenación (método MergeSort)

Profundizando un poco más en el tema de los algoritmos de ordenación y después de ver unos videos disponibles en la página web del MIT  he programado el algoritmo MergeSort utilizando listas enlazadas con punteros. Este algoritmo se comporta mucho mejor que el de selección cuando el número de elementos a ordenar crece. La idea que aplica este algoritmo es la de "divide y vencerás" y lo hace de modo recursivo.

struct tipo_dato {
    int num;
    struct tipo_dato *sig;
};



struct tipo_dato *mergeSort(struct tipo_dato *lista) {
    struct tipo_dato *lista1=NULL, *lista2=NULL, *listaOrd1=NULL, *listaOrd2=NULL, *listaOrd=NULL;


    if (longitud_lista(lista) <= 1) {
        return lista;
    }
    else {
        //Este es el puntero a la primera mitad de la lista.
        lista1 = lista;
        //Obtenemos la segunda parte de la lista (la segunda mitad).
        lista2 = obtener_lista2(lista);
        //Ordenamos recursivamente cada mitad del algoritmo
        listaOrd1 = mergeSort(lista1);
        listaOrd2 = mergeSort(lista2);

        //Mezclamos las dos mitades ordenadas previamente
        listaOrd = mezclar(listaOrd1, listaOrd2);

        return listaOrd;
    }
}

Para ver el código de un ejemplo de uso del algoritmo y los resultados de la ejecución podéis visitar este enlace en Codepad:
http://codepad.org/B3EOCoi8

Ordenación (método de selección)

Hemos estado hablando sobre los algoritmos de ordenación en clase y tuvimos que implementar el algoritmo de ordenación por selección para poder mostrar unos listados de datos ordenados en una aplicación que estamos realizando. A continuación muestro el código correspondiente a la función que realiza la tarea de la ordenación y la definición de la estructura de datos que representa los nodos de la lista enlazada.

struct tipo_lista_libro {
    char titulo[20];
    char autor[25];
    float precio;
    struct tipo_lista_libro *sig;
};

struct tipo_lista_libro *ordenar_lista_libros_seleccion(struct tipo_lista_libro *lista) {
    struct tipo_lista_libro *lista_aux = NULL, *lista_aux2 = NULL;
    struct tipo_lista_libro libro;

    lista_aux = lista;
    if (lista != NULL) {
        while (lista_aux->sig != NULL) {
            lista_aux2 = lista_aux->sig;
            while (lista_aux2 != NULL) {
                if (strcmp(lista_aux->titulo, lista_aux2->titulo)>0) {
                    //Copiamos el contenido de lista_aux a una variable temporal
                    strcpy(libro.titulo, lista_aux->titulo);
                    strcpy(libro.autor, lista_aux->autor);
                    libro.precio = lista_aux->precio;
                    //Copiamos el contenido de lista_aux2 a lista_aux
                    strcpy(lista_aux->titulo, lista_aux2->titulo);
                    strcpy(lista_aux->autor, lista_aux2->autor);
                    lista_aux->precio = lista_aux2->precio;
                    //Copiamos en lista_aux2 el contenido de la variable auxiliar
                    strcpy(lista_aux2->titulo, libro.titulo);
                    strcpy(lista_aux2->autor, libro.autor);
                    lista_aux2->precio = libro.precio;
                }
                lista_aux2 = lista_aux2->sig;
            }
            lista_aux = lista_aux->sig;
        }
    }
    return lista;
}

Para ver el resultado de una prueba de la ejecución de este programa visita el siguiente enlace:
http://codepad.org/qkNxYv08 en Codepad. Allí podéis ver el código completo y los resultados de la ejecución.