¡Hola! En este video aprenderemos el método de ordenamiento de Radix Sort
RadixSort
En la cabecera de nuestro programa vamos a llamar las librerias stdio.h y stdlib.h.
Antes de declarar las dos estructuras que vamos a utilizar,en la cabecera del programa vamos a escribir #define Nodo struct nodo y #define Lista struct lista, esto quiere decir que cada vez que escribamos la palabra “Nodo” nos estamos al nuevo tipo de dato que es struct nodo y la palabra “List” hace referencia a struct lista.
Declaramos la primera estructura Nodo la cual va a contener un dato y un Nodo apuntador al siguiente nodo.La estructura Lista está conformado por dos apuntadores de tipo Lista llamados inicio y final, los cuales nos indicarán el inicio y el final de cada lista que declaremos.
Se declara un arreglo de diez elementos de tipo Lista, para guardar e ir acomodando en cada ordenación según el dígito que sea el relevante del 0 al 9.
● Función digitoMax
Declaramos una función de tipo entero y va a recibir el arreglo como un apuntador y un número entero que representa el número de datos en el arreglo.
Declaramos dos datos de tipo entero,uno será el número máximo del arreglo (Max) ,que en un principio lo vamos a igualar al primer elemento del arreglo y el segundo será una variable para la función for ( i ).
Abrimos un for que vaya del 0 al números de datos menos 1 y con paso de 1, dentro abrimos un if con la condición: Si el dato en la posición i en nuestro arreglo es mayor que Max, entonces Max va ser el dato.Cerramos if, cerramos for y finalmente hacemos un return Max.
● Función desencolar
Declaramos una función de tipo Nodo apuntador y que tomará como parámetro una lista de tipo Lista apuntador, este será la lista desencolar.
Declaramos un Nodo apuntador auxiliar (aux).
En un if con condición: lista en su parte de inicio y lista en su parte de final sean iguales a NULL, en caso de ser verdadero significa que la lista está vacía y no hay ningún elemento a desencolar,por ello se hace un return NULL.Sino se cumple, entonces aux es igual al inicio de la lista,se recorre el apuntador inicio al nodo siguiente y aislamos el nodo aux haciendo su parte de siguiente NULL. Se abre otro if con la condición: Si inicio es NULL, entonces la lista se quedó vacía,así que el apuntador a final se iguala a NULL. Se cierra el segundo y primer if y se hace un return aux.
● Función Radix
Declaramos una función de tipo void con parámetros el arreglo de tipo entero apuntador y un dato entero que nos da el número de elementos del arreglo.
Declaramos un dato entero y lo igualamos a la función digitoMax para asignarle el número mayor del arreglo (Máximo), un dato de tipo entero que nos indicará con qué dígito estamos ordenando el arreglo y en un principio va ser igual a 1 (índice), una variable de tipo entero para el for ( i ) y un Nodo apuntador que apunta a NULL (n).
Con un for de 0 al 10 con paso de 1, vamos a un igualando cada espacio del arreglo de tipo lista que declaramos en un inicio con la función crearLista( ), para crear en sí una arreglo de lista.
Dentro de un while con la condición: El Máximo entre el índice sea mayor a 0,se abre un for de 0 al menos que el número de datos con paso de 1,donde vamos a llamar la función insertarNodo y le vamos a pasar como parámetro: empezando con “&” le pasamos el espacio del arreglo de lista donde la posición es el dígito a considerar en el dato (por ejemplo si estamos considerando el digito menos significativo de 19, entonces sería 9 y por lo tanto se guardaría en arreglo[9]) para ello en el entre corchetes ponemos la operación: dato entre el índice y su resultado sacamos su módulo entre 10, esto nos va a regresar el dígito del dato a considerar y por consiguiente la posición en el arreglo de listas, y a la función pasamos el dato.
Para acomodar las datos de nuevo en el arreglo,declaremos un dato entero y lo igualamos a 0 ( x ), dentro de un for desde 0 a menos que 10 con paso 1 abrimos un do- while, nuestro nodo apuntador que declaramos arriba lo igualamos a la función desencolar y le pasamos el parámetro el arreglo con “&” y entre corchetes la variable de for.
Abrimos un if con la condición que n sea diferentes de NULL , si se cumple vamos a guardar n es su parte de dato nuestro arreglo con índice x, le sumamos 1 a x y liberamos con free( ) la variable n.Cerramos el do-while con la condición: n sea diferente a NULL, imprimimos el arreglo con un for y al índice lo multiplicamos por 10,cerramos while y función.
● Función main
Declaramos tres variables enteros, una variable para el for, otro para el número de elementos del arreglo (N) y un apuntador que será nuestro arreglo.
Se leer el valor de N, guardamos en el apuntador el espacio para N enteros con malloc( ), con un for de 0 a menos que N vamos llenando con datos enteros nuestro arreglo y llamamos a la función Radix y le pasamos el arreglo y N.
Puedes encontrar el código fuente en el siguiente enlace:
Recuerda que siempre nos puedes contactar por vía correo electrónico.
Comments