Implementation (Part 1)
Lição 5 de 9 do curso Radix Sort - Série DSA da Coddy.
Construiremos o Radix Sort a partir de sua operação principal.
Desafio
MédioCada passagem do Radix Sort é um stable counting sort em um único dígito. Vamos construir isso primeiro.
Escreva uma função chamada countingSortByDigit que recebe um array de inteiros não negativos arr e um valor posicional exp (1 para unidades, 10 para dezenas, 100 para centenas, ...), e retorna um novo array ordenado pelo dígito (x / exp) % 10. A ordenação deve ser estável: elementos com o mesmo dígito mantêm sua ordem original.
Por exemplo, countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) retorna [170, 90, 2, 802, 24, 45, 75, 66] (ordenado pelo dígito das unidades).
Experimente você mesmo
#include <stdlib.h>
int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
// Escreva o código aqui
*returnSize = arr_size;
return arr;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Radix Sort - Série DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity