Clasificación Radix en Python

En este tutorial, veremos la teoría y la implementación de Radix Sort en Python, así como Counting Sort como su subrutina principal, con ejemplos ilustrados.

Introducción a Radix Sort

La raíz (o base) es la cantidad de dígitos que se usa para representar números en un sistema numérico posicional. Para el sistema binario, la base es 2 (utiliza solo dos dígitos: 0 y 1). Para el sistema decimal, la base es 10 (utiliza diez dígitos para representar todos los números, del 0 al 9).

Un sistema de numeración posicional es, en términos simples, un sistema de escritura de números, donde el peso (o el valor) de un dígito está determinado por su posición. Por ejemplo, en el número ‘123’, ‘1’ tiene más valor que ‘3’ porque está en una posición que denota centenas, y ‘2’ está en las decenas.

Radix Sort se puede usar para ordenar lexicográficamente muchos tipos de datos: enteros, palabras, correos electrónicos, pero se usa principalmente para ordenar colecciones de enteros y cadenas (que se asignan a claves enteras apropiadas).

Es un algoritmo de clasificación no comparativo, lo que significa que no clasifica una colección comparando sus elementos individuales, sino que utiliza la naturaleza inherente de los datos que clasifica para clasificar más rápido: clasifica los datos en función de su radix .

Los algoritmos de clasificación comparativa tienen la mejor complejidad de tiempo de caso de O(nlogn), que es comparativamente peor que el tiempo de ejecución lineal (O(n+k)) de algoritmos no comparativos.

Por ejemplo, sea n el número de elementos a ordenar y k sea el rango de valores de elementos permitidos.

Tiempo de conteo (un popular algoritmo no comparativo) tiene la complejidad de O(n+k) cuando k está en el rango de 1..n. Pero, si los elementos van desde 1..n², entonces la complejidad aumenta a O(n²), que es peor que cualquier algoritmo de clasificación comparativa.

Counting Sort tiene el potencial de ser significativamente más rápido que otros algoritmos comparativos populares, sin embargo, solo si se cumple una determinada condición.

La idea de Radix Sort es actualizar Counting Sort para que mantenga la complejidad del tiempo lineal incluso si el rango de valores de los elementos supera drásticamente la cantidad de elementos.

De hecho, Radix Sort usa inherentemente Counting Sort como la subrutina principal, con algunos ajustes para superar los problemas que surgen con un rango aumentado de valores de elementos.

Algoritmo de clasificación por conteo

Para comprender Radix Sort, primero tendremos que profundizar en Counting Sort, implementarlo y observar la caída con un mayor número de valores de elementos.

¿Por qué usar la ordenación por conteo en la ordenación Radix? {#por qué usar el conteo en el ordenamiento de radix}

La ordenación por conteo es un algoritmo de ordenación estable, no comparativo, y se utiliza principalmente para ordenar matrices de enteros. Todas estas características son importantes para su uso en Radix Sort. Sin embargo, puede usar otros algoritmos como subrutina, siempre que tengan estas características, Counting Sort es la combinación más natural.

Radix Sort necesita mantener un orden relativo de elementos con los mismos valores clave en la matriz de entrada mientras ordena los mismos dígitos de valor de lugar, por lo tanto, nuestra subrutina principal, por definición, debe ser algún tipo de algoritmo de clasificación estable:

ilustración de clasificación estable

Los algoritmos de clasificación no comparativa generalmente tienen una complejidad lineal, por lo que tendrán un impacto menor en la complejidad de Radix Sort.

¿Cómo funciona la ordenación por conteo?

Echemos un vistazo a una matriz de enteros sin ordenar, que ordenaremos usando la ordenación por conteo:

1
I = [2, 2, 0, 6, 1, 9, 9, 7]

Counting Sort funciona contando el número de elementos, que se ajustan a un valor de clave distinto, y luego calcula las posiciones de cada clave.

En primer lugar, encontraremos el elemento máximo en la matriz de entrada: max = 9.

Luego, crearemos una matriz auxiliar con elementos max+1. Este es el arreglo de conteo (C), que se usará para almacenar el número de ocurrencias de cada elemento en el arreglo de entrada.

Inicialmente, todas las cuentas se inicializan a 0:

1
2
     C = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # Count array     
#indices: 0  1  2  3  4  5  6  7  8  9

*** Ahora, tenemos que seguir los siguientes pasos: ***

1. Recorra la matriz de entrada y aumente el recuento correspondiente para cada elemento en 1

Por ejemplo, si encontramos un elemento con el valor 2 en la matriz de entrada (I), sumamos 1 al elemento con el índice 2 en la matriz de recuento:

1
2
3
4
5
    I = [2, 2, 0, 6, 1, 9, 9, 7] # The first element is 2
         ^
        
    C = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0] # We increase count of 2nd element by 1
#indices: 0  1  2  3  4  5  6  7  8  9

Después de este paso, el arreglo de conteo almacenará el número de ocurrencias de cada elemento en el arreglo de entrada:

1
2
3
4
5
6
7
     C = [1, 1, 2, 0, 0, 0, 1, 1, 0, 2] 
#indices: 0  1  2  3  4  5  6  7  8  9
   
# Element 0 has 1 occurrence
# Element 1 has 1 occurrence
# Element 2 has 2 occurrences 
# Element 3 has no occurrences...

2. Para cada elemento en la matriz de conteo, sume su valor con el valor de todos sus elementos anteriores y luego almacene ese valor como el valor del elemento actual:

1
2
3
4
5
6
7
     C = [1, 2, 4, 4, 4, 4, 5, 6, 6, 8] 
#indices: 0  1  2  3  4  5  6  7  8  9
# Element  0 = 1
# Element  1 = 1 + 1
# Element  2 = 1 + 1 + 2
# Element  3 = 1 + 1 + 2 + 0
#...

De esta manera, estamos almacenando la suma acumulada de los elementos de la arreglo de conteo, en cada paso.

3. Calcular la posición del elemento en función de los valores de la matriz de conteo

Para almacenar esta secuencia ordenada, necesitaremos crear una nueva matriz. Llamémoslo el arreglo de salida (O), e inicialícelo con k ceros, donde k es el número de elementos en el arreglo de entrada:

1
2
     O = [0, 0, 0, 0, 0, 0, 0, 0] // Initialized output array
#indices: 0  1  2  3  4  5  6  7 

Para cada elemento I[i] (comenzando desde el final) en la matriz de entrada:

  1. Encuentre el índice en la matriz de conteo que es igual al valor del elemento actual I[i]
    • That's the element C[j] where j=I[i]
  2. Resta 1 del valor de C[i]
    • Now we have newValue = C[i]-1
  3. Guarde I[i] en O[newValue]
  4. Actualice C[i] con newValue

clasificación de conteo visualizada

¡Al final, la matriz de salida contiene los elementos ordenados de la matriz de entrada!

Implementación de ordenación por conteo en Python

Ahora, con todo eso fuera del camino, avancemos e implementemos Counting Sort en Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def countingSort(inputArray):
    # Find the maximum element in the inputArray
    maxEl = max(inputArray)

    countArrayLength = maxEl+1

    # Initialize the countArray with (max+1) zeros
    countArray = [0] * countArrayLength

    # Step 1 -> Traverse the inputArray and increase 
    # the corresponding count for every element by 1
    for el in inputArray: 
        countArray[el] += 1

    # Step 2 -> For each element in the countArray, 
    # sum up its value with the value of the previous 
    # element, and then store that value 
    # as the value of the current element
    for i in range(1, countArrayLength):
        countArray[i] += countArray[i-1] 

    # Step 3 -> Calculate element position
    # based on the countArray values
    outputArray = [0] * len(inputArray)
    i = len(inputArray) - 1
    while i >= 0:
        currentEl = inputArray[i]
        countArray[currentEl] -= 1
        newPosition = countArray[currentEl]
        outputArray[newPosition] = currentEl
        i -= 1

    return outputArray

inputArray = [2,2,0,6,1,9,9,7]
print("Input array = ", inputArray)

sortedArray = countingSort(inputArray)
print("Counting sort result = ", sortedArray)

Ejecutar el código anterior nos dará el siguiente resultado:

1
2
Input array =  [2, 2, 0, 6, 1, 9, 9, 7]
Counting sort result =  [0, 1, 2, 2, 6, 7, 9, 9]

Complejidad de clasificación de conteo

La complejidad temporal de la clasificación de conteo es O(n+k), donde n es el número de elementos en el arreglo de entrada, y k es el valor del elemento max en el arreglo.

El problema ocurre cuando el valor del elemento más grande supera drásticamente la cantidad de elementos en la matriz. A medida que k se acerca a , la complejidad de tiempo se acerca a O(n²), que es una complejidad de tiempo horrible para un algoritmo de clasificación.

Aquí es donde entra en juego Radix Sort.

Algoritmo de clasificación Radix

En lugar de contar los elementos por su valor clave distinto, Radix Sort agrupa los dígitos por su valor posicional y realiza la clasificación por conteo en cada grupo. La posición inicial puede variar: LSD (Dígitos menos significativos) o MSD (Dígitos más significativos) son dos comunes y, en consecuencia, estas variaciones de Radix Sort se denominan LSD Radix Sort y MSD Radix Sort.

Sea I = [2, 20, 61, 997, 1, 619] la matriz de entrada que queremos ordenar:

agrupación por ordenación radix visualizada

Nos centraremos en LSD Radix Sort.

Algoritmo de clasificación Radix

Los pasos tomados por Radix Sort son bastante sencillos:

  1. Encuentra el elemento máximo en la matriz de entrada - max = 997
  2. Encuentra el número de dígitos en el elemento max - D = 3
  3. Inicializa el valor posicional al lugar menos significativo - placeVal = 1
  4. Para los tiempos D haz lo siguiente:
    1. Perform the counting sort by the current place value
    2. Move to the next place value by multiplying placeVal by 10

radix suerte

Implementando Radix Sort en Python

Y finalmente, con eso fuera del camino, implementemos Radix Sort en Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def countingSortForRadix(inputArray, placeValue):
    # We can assume that the number of digits used to represent
    # all numbers on the placeValue position is not grater than 10
    countArray = [0] * 10
    inputSize = len(inputArray)

    # placeElement is the value of the current place value
    # of the current element, e.g. if the current element is
    # 123, and the place value is 10, the placeElement is
    # equal to 2
    for i in range(inputSize): 
        placeElement = (inputArray[i] // placeValue) % 10
        countArray[placeElement] += 1

    for i in range(1, 10):
        countArray[i] += countArray[i-1]

    # Reconstructing the output array
    outputArray = [0] * inputSize
    i = inputSize - 1
    while i >= 0:
        currentEl = inputArray[i]
        placeElement = (inputArray[i] // placeValue) % 10
        countArray[placeElement] -= 1
        newPosition = countArray[placeElement]
        outputArray[newPosition] = currentEl
        i -= 1
        
    return outputArray

def radixSort(inputArray):
    # Step 1 -> Find the maximum element in the input array
    maxEl = max(inputArray)

    # Step 2 -> Find the number of digits in the `max` element
    D = 1
    while maxEl > 0:
        maxEl /= 10
        D += 1
    
    # Step 3 -> Initialize the place value to the least significant place
    placeVal = 1

    # Step 4
    outputArray = inputArray
    while D > 0:
        outputArray = countingSortForRadix(outputArray, placeVal)
        placeVal *= 10  
        D -= 1

    return outputArray
    
input = [2,20,61,997,1,619]
print(input)
sorted = radixSort(input)
print(sorted)

Ejecutar el código anterior nos dará el siguiente resultado:

1
2
[2, 20, 61, 997, 1, 619]
[1, 2, 20, 61, 619, 997]

Complejidad de clasificación Radix

Como dijimos antes, Radix Sort tiene complejidad de tiempo lineal. Si usamos Counting Sort como la subrutina principal, la complejidad de la ordenación por base es O(d(n+k)). Esto se debe a que estamos ejecutando la ordenación de conteo d veces, y la complejidad de la Ordenación de conteo en sí misma es O(n+k).

Conclusión

Radix sort es un excelente algoritmo de clasificación para usar en algunos casos específicos. Algunos puntos de referencia incluso han demostrado que la clasificación radix puede ejecutarse hasta 3 veces más rápido que otros algoritmos de clasificación de uso más general.

Brilla cuando la matriz de entrada tiene claves más cortas o el rango de los valores de los elementos es más pequeño. Pero tiene poca complejidad espacial en otros casos, cuando el rango de valores de los elementos es bastante grande y los elementos tienen demasiados dígitos en su representación.

Esa es la razón principal por la que la clasificación radix no se usa tan ampliamente como otros tipos de algoritmos de clasificación, incluso si tiene una complejidad de tiempo lineal.

Licensed under CC BY-NC-SA 4.0