Clasificación de pila de Python

1. Algoritmo de clasificación de montón en Python
2. Implementar el algoritmo de clasificación de almacenamiento dinámico en Python

Este tutorial mostrará la implementación del algoritmo de clasificación de almacenamiento dinámico en Python.

Algoritmo de clasificación de montón en Python

Heap sort es un algoritmo robusto para clasificar matrices y listas en Python. Es popular porque es muy rápido y no ocupa espacio adicional como la ordenación por fusión y la ordenación rápida.

La complejidad temporal de la ordenación del montón es O(n*log(n)).

El heap sort es un algoritmo en el lugar que no crea más estructuras de datos para guardar los estados intermedios de los datos. En cambio, realiza cambios en nuestra matriz original.

Por lo tanto, esto nos ahorra mucho espacio cuando los datos son muy grandes.

La única desventaja de este algoritmo es que es muy inestable. Si tenemos varios elementos en nuestra matriz con el mismo valor en diferentes índices, sus ubicaciones cambiarán durante la clasificación.

El algoritmo de ordenación del montón funciona creando recursivamente un mín o un montón máximo, sacando el nodo raíz, colocándolo en el primer índice no ordenado en nuestra matriz y convirtiendo el último elemento del montón en el nodo raíz.

Este proceso se repite recursivamente hasta que nos queda un solo nodo dentro de nuestro montón. Al final, el último elemento del montón se coloca en el último índice de nuestra matriz.

Si lo pensamos por un segundo, este proceso se parece al algoritmo de ordenación por selección, ya que tomamos los valores más grandes o más pequeños y los colocamos en la parte superior de nuestra matriz ordenada.

Implementar el algoritmo de clasificación de almacenamiento dinámico en Python

Primero veremos cómo implementar la función build_heap() que toma la matriz original, la longitud de la matriz y el índice de nuestro nodo principal. Aquí, si observamos una matriz, el índice del último nodo principal se encuentra en (n//2 - 1) dentro de nuestra matriz.

De manera similar, el índice para el hijo izquierdo de ese padre específico es 2*parent_index + 1, y el índice para el hijo derecho es 2*parent_index + 2.

En este ejemplo, estamos tratando de crear un montón máximo. Eso significa que cada nodo principal debe ser mayor que sus nodos secundarios.

Para esto, comenzaremos desde el último nodo principal y nos moveremos hacia arriba hasta el nodo raíz de nuestro montón. Si quisiéramos crear un montón mínimo, querríamos que todos nuestros nodos principales fueran más pequeños que sus nodos secundarios.

Esta función build_heap() verificará si el hijo izquierdo o derecho es mayor que el nodo principal actual e intercambiará el nodo mayor con el nodo principal.

Esta función se llama a sí misma recursivamente porque queremos repetir el proceso anterior de manera incremental para todos los nodos principales en nuestro montón.

El siguiente fragmento de código demuestra una implementación funcional de la función built_heap() mencionada anteriormente en Python.

def build_heap(arr, length, parent_index):
    largest_index = parent_index
    left_index = 2 * parent_index + 1
    right_index = 2 * parent_index + 2

    if left_index < length and arr[parent_index] < arr[left_index]:
        largest_index = left_index

    if right_index < length and arr[largest_index] < arr[right_index]:
        largest_index = right_index

    if largest_index != parent_index:
        arr[parent_index], arr[largest_index] = arr[largest_index], arr[parent_index]

        build_heap(arr, length, largest_index)

Ahora, tenemos una función que toma el valor máximo dentro de nuestra matriz y lo coloca en la raíz de nuestro montón. Necesitamos una función que tome la matriz desordenada, llame a la función build_heap() y extraiga elementos del montón.

El siguiente fragmento de código demuestra la implementación de la función heapSort() en Python.

def heapSort(arr):
    length = len(arr)

    for parent_index in range(length // 2 - 1, -1, -1):
        build_heap(arr, length, parent_index)

    for element_index in range(length - 1, 0, -1):
        arr[element_index], arr[0] = arr[0], arr[element_index]
        build_heap(arr, element_index, 0)

Llamamos incrementalmente a la función build_heap() de cada nodo principal dentro de nuestra matriz. Tenga en cuenta que estamos dando longitud//2-1 como índice inicial y -1 como índice final, con un paso de -1.

Esto significa que comenzamos desde el último nodo principal y disminuimos gradualmente nuestro índice en 1 hasta llegar al nodo raíz.

El segundo bucle for extrae elementos de nuestro montón. También comienza desde el último índice y se detiene en el primer índice de nuestra matriz.

Intercambiamos el primer y el último elemento de nuestra matriz en este bucle y ejecutamos la función build_heap() en la matriz recién ordenada pasando 0 como índice raíz.

Ahora, hemos escrito nuestro programa para implementar heap sort en Python. Es hora de ordenar una matriz y probar el código escrito anteriormente.

arr = [5, 3, 4, 2, 1, 6]
heapSort(arr)
print("Sorted array :", arr)

Producción :

Sorted array : [1, 2, 3, 4, 5, 6]

Como podemos ver, nuestra matriz está completamente ordenada. Esto significa que nuestro código funciona bien.

Si queremos ordenar en orden descendente, podemos crear un montón mínimo en lugar del montón máximo implementado anteriormente.

Este artículo no explicará el montón mínimo porque ya discutió qué es un montón mínimo al comienzo de este tutorial.

Nuestro programa funciona de la siguiente manera. El siguiente bloque muestra el estado de nuestra matriz en cada etapa de la ejecución del código.

Original Array [5, 3, 4, 2, 1, 6] # input array
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 1
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 2
Building Heap [6, 3, 5, 2, 1, 4] # after build_heap() pass 3
Extracting Elements [6, 3, 5, 2, 1, 4] # before swapping and build_heap pass 1
Extracting Elements [5, 3, 4, 2, 1, 6] # before swapping and build_heap pass 2
Extracting Elements [4, 3, 1, 2, 5, 6] # before swapping and build_heap pass 3
Extracting Elements [3, 2, 1, 4, 5, 6] # before swapping and build_heap pass 4
Extracting Elements [2, 1, 3, 4, 5, 6] # before swapping and build_heap pass 5
Sorted array : [1, 2, 3, 4, 5, 6] # after swapping and build_heap pass 5

La función build_heap() se ejecuta 3 veces porque solo hay 3 nodos principales en nuestro montón.

Después de eso, nuestra fase de extracción de elementos toma el primer elemento, lo intercambia con el último elemento y ejecuta la función build_heap() nuevamente. Este proceso se repite para longitud - 1, y nuestra matriz se ordena.