Ordenar por conteo en Python

En esta guía, veremos la teoría detrás de Counting Sort y la implementaremos en Python, así como también analizaremos su complejidad de tiempo y espacio.

Introducción

La ordenación por conteo es un algoritmo de ordenación que se utiliza para ordenar los elementos de una matriz en tiempo lineal. Por lo general, usamos Counting Sort para ordenar matrices de enteros.

Recuento Ordena un **algoritmo estable, no comparativo.

Los algoritmos de clasificación no comparativos realizan la clasificación sin ninguna comparación entre los elementos que se van a clasificar.

Los algoritmos de clasificación estables conservan el orden relativo de los elementos con el mismo valor en la matriz ordenada. Eso significa que el orden relativo de dos elementos del mismo valor en la matriz original será el mismo que su orden relativo en la matriz ordenada.

Clasificación estable

La ordenación por conteo no es un algoritmo en el lugar, utiliza una matriz auxiliar para ordenar los elementos de una matriz de entrada.

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

Primero echemos un vistazo intuitivo a cómo funciona el algoritmo.

Supongamos que tenemos el arreglo I = [2, 2, 0, 6, 1, 9, 9, 7] y queremos ordenarlo. Llamaremos a la matriz I la matriz de entrada.

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, necesitamos encontrar el elemento con el valor más alto, lo llamaremos el elemento máximo - maxElement = 9.

Luego, crearemos una matriz auxiliar con elementos maxElement+1, llamada matriz count (C). Lo usaremos para almacenar el número de ocurrencias de cada elemento individual en la matriz de entrada I. Por lo tanto, todos los conteos deben inicializarse 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. Repasa cada elemento de la matriz de entrada y aumenta su cuenta correspondiente 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 recuento, sume su valor con el valor de todos sus elementos anteriores y 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. Calcule 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. Encuentra el índice en el arreglo de conteo que es igual al valor del elemento actual I[i]
  • Ese es el elemento C[j] donde j=I[i]
  1. Resta 1 del valor de C[i]
  • Ahora tenemos nuevoValor = C[i]-1
  1. Guarda el I[i] en O[newValue]
  2. Actualizar C[i] con newValue

Ordenar conteo

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

Clasificación por recuento: implementación de Python

Ahora, con todo eso fuera del camino, sigamos adelante 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
    maxElement= max(inputArray)

    countArrayLength = maxElement+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 producirá 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]

La complejidad del algoritmo de clasificación de conteo {#la complejidad del algoritmo de clasificación de conteo}

El algoritmo de ordenación Counting utiliza solo bucles simples for y while sin recurrencias complejas ni llamadas a subrutinas, por lo tanto, su análisis de complejidad es un proceso bastante sencillo.

Antes de sumergirnos en el análisis de complejidad, etiquetemos la longitud de la matriz de entrada como n y el valor del elemento máximo en la matriz de entrada como k.

Complejidad del tiempo

El primer paso del algoritmo itera sobre la matriz de entrada n veces para inicializar la matriz de recuento, por lo que tiene la complejidad de O(n).

El segundo paso itera sobre el conteo multiplicado por k veces para calcular la suma acumulada de cada elemento, por lo que tiene la complejidad de O(k).

El tercer paso realiza la clasificación en función de la matriz de conteo, por lo que tiene que iterar en un ciclo while n veces, por lo que tiene la complejidad de O(n).

Colectivamente, la complejidad de tiempo del algoritmo Counting Sort es O(n+k).

Complejidad espacial

La ordenación por conteo usa entrada y arreglo de salida, ambos de longitud n y un arreglo de conteo de longitud (k+1).

Por lo tanto, el espacio total que utiliza este algoritmo es O(n+k).

Conclusión

Con todo, Counting Sort es un algoritmo de clasificación excelente y eficiente, pero simple. En circunstancias ideales, es realmente fácil de entender y aprender, pero aun así se las arregla para mantener la complejidad lineal.

El problema real ocurre cuando el valor del elemento más grande k excede el número de elementos en la matriz de entrada n. A medida que k se acerca a , la complejidad de tiempo de la ordenación por conteo se acerca a O(n²), que es una complejidad de tiempo horrible para un algoritmo de ordenación. Por lo tanto, no se recomienda usar la ordenación por conteo si la matriz de entrada tiene un amplio rango de valores.

Idealmente, usaremos Counting Sort para ordenar algunos arreglos enteros con un pequeño rango de valores o como una subrutina para algún otro algoritmo de clasificación, como Clasificación Radix. De esa manera, nos aseguraremos de maximizar todo el potencial del tipo de conteo, mientras evitamos todos los casos de uso subóptimos.

Licensed under CC BY-NC-SA 4.0