Implementation (Part 1)
Lección 5 de 9 del curso Radix Sort - Serie de DSA de Coddy.
Construiremos Radix Sort partiendo de su operación fundamental.
Desafío
IntermedioCada pasada de Radix Sort es un ordenamiento por conteo estable (stable counting sort) sobre un solo dígito. Vamos a construir eso primero.
Escribe una función llamada countingSortByDigit que reciba un arreglo de enteros no negativos arr y un valor posicional exp (1 para las unidades, 10 para las decenas, 100 para las centenas, ...), y devuelva un nuevo arreglo ordenado por el dígito (x / exp) % 10. El ordenamiento debe ser estable: los elementos con el mismo dígito deben mantener su orden original.
Por ejemplo, countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) devuelve [170, 90, 2, 802, 24, 45, 75, 66] (ordenado por el dígito de las unidades).
Pruébalo tú mismo
#include <stdlib.h>
int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
// Escribe el código aquí
*returnSize = arr_size;
return arr;
}
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Radix Sort - Serie de DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity