Neste tutorial, você aprenderá como funciona a ordenação de raiz. Além disso, você encontrará exemplos de trabalho de classificação raiz em C, C ++, Java e Python.
A classificação radix é uma técnica de classificação que classifica os elementos agrupando primeiro os dígitos individuais do mesmo valor de posição . Em seguida, classifique os elementos de acordo com sua ordem crescente / decrescente.
Suponha que temos um array de 8 elementos. Primeiro, classificaremos os elementos com base no valor da casa da unidade. Em seguida, classificaremos os elementos com base no valor da décima casa. Esse processo segue até o último lugar significativo.
Deixe a matriz inicial ser (121, 432, 564, 23, 1, 45, 788). Ele é classificado de acordo com a classificação raiz, conforme mostrado na figura abaixo.
Trabalho de Radix Sort
Consulte a classificação por contagem antes de ler este artigo porque a classificação por contagem é usada como uma classificação intermediária na classificação raiz.
Como funciona o Radix Sort?
- Encontre o maior elemento na matriz, ou seja, máx. Let
XSer o número de dígitos emmax.Xé calculado porque temos que passar por todos os lugares significativos de todos os elementos.
Nesta matriz(121, 432, 564, 23, 1, 45, 788), temos o maior número 788. Possui 3 dígitos. Portanto, o loop deve ir até a casa das centenas (3 vezes). - Agora, passe por cada lugar significativo, um por um.
Use qualquer técnica de classificação estável para classificar os dígitos em cada lugar significativo. Usamos classificação de contagem para isso.
Classifique os elementos com base nos dígitos do local da unidade (X=0).
Usando a classificação por contagem para classificar os elementos com base no local da unidade - Agora, classifique os elementos com base nos dígitos na casa das dezenas.
Classifique os elementos com base na casa das dezenas - Finalmente, classifique os elementos com base nos dígitos na casa das centenas.
Classifique os elementos com base em centenas de lugares
Algoritmo de classificação de raiz
radixSort (array) d <- número máximo de dígitos no maior elemento cria d buckets de tamanho 0-9 para i <- 0 a d classifica os elementos de acordo com os i-ésimos dígitos do lugar usando countSort countSort (array, d) max <- find maior elemento entre os elementos da d-ésima casa inicializar a matriz de contagem com todos os zeros para j <- 0 para dimensionar encontrar a contagem total de cada dígito único na d-ésima casa dos elementos e armazenar a contagem no j-ésimo índice na matriz de contagem para i <- 1 para encontrar o máximo a soma cumulativa e armazena-a no próprio array de contagem para j <- tamanho reduzido para 1 restaura os elementos para o array diminui a contagem de cada elemento restaurado em 1
Exemplos de Python, Java e C / C ++
Python Java C C ++ # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data)
// Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
// Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
Complexidade
Como a ordenação de raiz é um algoritmo não comparativo, tem vantagens sobre os algoritmos de ordenação comparativa.
Para a classificação básica que usa classificação por contagem como uma classificação estável intermediária, a complexidade do tempo é O(d(n+k)).
Aqui destá o ciclo numérico e O(n+k)a complexidade de tempo da classificação de contagem.
Assim, a ordenação de raiz tem complexidade de tempo linear que é melhor do que O(nlog n)algoritmos de ordenação comparativa.
Se tomarmos números de dígitos muito grandes ou o número de outras bases, como números de 32 e 64 bits, então ele pode funcionar em tempo linear, embora a classificação intermediária ocupe um grande espaço.
Isso torna o espaço de classificação raiz ineficiente. Esta é a razão pela qual esse tipo não é usado em bibliotecas de software.
Aplicativos de classificação de raiz
A classificação Radix é implementada em
- Algoritmo DC3 (Kärkkäinen-Sanders-Burkhardt) ao fazer uma matriz de sufixo.
- lugares onde há números em grandes intervalos.
