Saltar al contenido

¿Cómo funciona Radix Sort?

Nuestros mejores desarrolladores agotaron sus provisiones de café, investigando noche y día por la resolución, hasta que Gabriel halló el arreglo en GitLab y hoy la compartimos con nosotros.

Solución:

En matemáticas, radix significa base, donde decimal sería base 10. Imagina que tienes números, algunos de los cuales tienen más de un dígito como

5, 213, 55, 21, 2334, 31, 20, 430

Para simplificar, supongamos que desea utilizar la base decimal (=10) para ordenar. Luego empezarías separando los números por unidades y luego volviéndolos a juntar; luego separarías los números por decenas y luego los juntarías de nuevo; luego por centenas y así sucesivamente hasta ordenar todos los números. Cada vez que haga un bucle, simplemente lea la lista de izquierda a derecha. También puedes imaginar que estás separando los números en cubos. Aquí hay una ilustración usando 5, 213, 55, 21, 2334, 31, 20, 430

Separar por unidades:

  • ceros: 20, 430

  • unos: 21, 31

  • dos:

  • tres: 213

  • cuatro patas: 2334

  • cincos: 5, 55

    De nuevo juntos: 20, 430, 21, 31, 213, 2334, 5, 55

Para volver a armarlos, primero lea el zeroes cubo, entonces el ones balde, luego así sucesivamente, hasta que lea el nines balde.

Separar por decenas:

  • ceros: 05

  • unos: 213

  • dos: 20, 21

  • tres: 430, 31, 2334,

  • cuatro patas:

  • cincos: 55

    De nuevo juntos: 5, 213, 20, 21, 430, 31, 2334, 55

Separar por centenas:

  • ceros: 005, 020, 021, 031, 055

  • unos:

  • dos: 213

  • tríos: 2334

  • cuatro patas: 430

  • cincos:

    De nuevo juntos: 5, 20, 21, 31, 55, 213, 2334, 430

Separar por miles:

  • ceros: 0005, 0020, 0021, 0031, 0055, 0213, 0430

  • unos:

  • dos: 2334

  • tres:

  • cuatro patas:

  • cincos:

    De nuevo juntos: 5, 20, 21, 31, 55, 213, 430, 2334

Ya has terminado. Vi un buen código para esto en Geekviewpoint tanto en Java como en Python

Piensa en una baraja de cartas. Primero lo ordenas por palo en cuatro montones. Luego coloca esos cuatro montones uno encima del otro y ahora los clasifica en 13 montones según el rango. Póngalos juntos y ahora tiene una baraja ordenada.

Este es el flujo básico de Quicksort.

Para el 1er pase: clasificamos el array sobre la base del dígito menos significativo (1s lugar) utilizando la ordenación por conteo. Observe que 435 está por debajo de 835, porque 435 se encontraba por debajo de 835 en la lista original.

Para el segundo pase: clasificamos el array sobre la base del siguiente dígito (lugar de 10) utilizando la ordenación por conteo. Observe que aquí 608 está por debajo de 704, porque 608 se encontraba por debajo de 704 en la lista anterior, y de manera similar para (835, 435) y (751, 453).

Para el 3er paso: clasificamos el array sobre la base del dígito más significativo (el lugar de las centenas) usando la ordenación por conteo. Observe que aquí 435 está por debajo de 453, porque 435 se encontraba por debajo de 453 en la lista anterior, y de manera similar para (608, 690) y (704, 751).

Para obtener más detalles, puede consultar este blog en codingeek y tener una comprensión clara.

Acuérdate de que te brindamos la opción de agregar una reseña .

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *