¡Hola! En este video aprenderemos el método de ordenamiento de Radix Sort
Merge Sort
En este caso vamos a utilizar una lista simple enlazada.
Encabezado y estructura de nuestro nodo
Función longitud_Lista
Vamos a declarar una función de tipo int con parámetro de dato Nodo de tipo apuntador hacia el inicio de una lista,es la variable longitud la que nos contará el número de elementos de la lista cada vez que se vaya recorriendo por otro Nodo apuntador llamado aux, cada nodo hasta que este sea NULL.
Función obtener_lista2
Declaramos una función de tipo Nodo puntero y como parámetro de entrada pasamos un Nodo apuntador.
Declaramos dos datos Nodos tipo apuntador:
list - Será nuestra nueva lista, la cual vamos a asignarle un espacio en memoria.
aux - Nos ayudará a recorrer la lista hasta encontrar la mitad de está. En un inicio será igual al Nodo apuntador que pasamos como parámetro.
Vamos a iniciar una varible de tipo entero que vamos a igualar con la función longitud_lista para sacar la longitud de la lista.
Vamos a dividir la longitud entre de dos y su resultado lo igualamos a una variable de tipo entero que nos guardará este dato que es la mitad de la lista. Si la longitud es impar el resultado de la división se le sumará uno.
Con un while vamos a ir recorriendo nuestro auxiliar el número de la variable mitad.
Ya situados ahí nuestra variable list, la igualamos a aux en su parte de siguiente y aislamos la nueva lista igualando aux en su parte de siguiente como NULL.
Regresamos list
Ejemplo cómo quedaría cada apuntador y la creación de una segunda lista
Función mergeSort
Vamos a declarar una función de tipo Nodo apuntador que le vamos a pasar el nodo inicial de nuestra lista.
Declaramos 5 apuntadores de tipo Nodo, cada una va a representar una lista.
Con un if vamos a considerar como base que la lista tenga más de un elemento ya que si solo tuviera solo 1, la lista ya estaría ordenada.
Nuestro primer apuntador se igualará a parámetro.
El segundo apuntador se igualará con la función obtener_lista2 que le pasaremos nuestro nuestro parámetro.
De forma recursiva vamos a igualar un tercer apuntador con la función mergeSort y le pasamos nuestro primer apuntador,así también nuestro cuarto apuntador lo igualamos con la función y le pasamos nuestro segundo apuntador.
Por último igualamos nuestro último apuntador con la función mezclar que nos dará la lista ya ordenada y le pasaremos el tercer y cuarto apuntador.
Regresaremos el quinto apuntador que tendrá la lista ordenada.
Lista Ordenada
Función mezclar
Vamos a declarar una función apuntador tipo Nodo con parámetro dos Nodo apuntador que son los inicios de las dos listas a mezclar.
Asignamos a dos variables apuntadores tipo Nodo a cada parámetro, en este caso aux1 y aux2. Estos nos ayudarán a recorrer las dos listas. Y otra variable del mismo tipo llamado lista_ordenada que será la mezcla de las dos listas.
Listas ya ordenadas antes del resultado final
Dentro de un while con la condición que ningún apuntador (aux1 y aux2) sean NULL. Después vamos a hacer la comparación de los datos que están señalando los apuntadores auxiliares para saber cual de los dos es el menor,cuando se sepa se debe insertar este valor en la lista de la variable lista_ordenada. Y recorremos el auxiliar al nodo siguiente,solo de la lista donde se sacó el nodo para insertarlo en la lista_ordenada.
Proceso de ordenación
Si un aux apunta a NULL significa que una lista se acabó,así que solo falta ir agregando los nodos restantes de la otra lista, esto se puede hacer con un while.
Finalmente regresamos lista_ordenada.
Comments