¿Qué es Quicksort??

Quicksort es uno de los algoritmos de clasificación eficientes. El algoritmo realiza la clasificación aplicando el paradigma de división y conquistar. Considere una matriz a [1 ... n] de n elementos. El algoritmo divide la matriz A en un índice Q de tal manera que todos los elementos en la subarray izquierda del índice son menores que el elemento en el índice Q (A [Q]), y todos los elementos en la subarray derecha son mayores que un [P]. Ahora, el algoritmo clasifica de manera recursiva a los dos subadarrines A [1 ... Q-1] y un [q+1 ... n] en el lugar llamando a la función Quicksort. Para obtener el índice Q, el algoritmo utiliza una función de partición.

La función de partición es una función que toma en una matriz a [l ... u] como entrada. Aquí, l es el límite inferior y u es el límite superior de la matriz. El algoritmo encuentra un índice Q de tal manera que todos los elementos menores de una [q] caen en la subarrray a [l ... q-1], y todos los elementos mayores que una [q] caen en la subarray a [q+1 ... u]. La función de partición logra esto usando un elemento pivote y dos punteros: puntero I y puntero j a la matriz.

El puntero j apunta al primer elemento en la matriz, y el puntero I se inicializa como J-1. La función itera a través de la matriz usando Pointer J. Para el elemento a [j], el elemento puede ser mayor que el elemento pivote o menos que el elemento pivote. Si el elemento es mayor que el elemento pivote, el puntero J se incrementa, apuntando al siguiente elemento. Si el elemento a [j] es menor que el elemento pivote, incrementamos el puntero I, intercambiamos un [i] y a [j]. El intercambio de los elementos ayuda a mantener el puntero I tal que los elementos hasta el elemento señalado por el puntero I son menos que el elemento pivote. Como paso final, la función de partición intercambia el elemento pivote con el elemento en el índice i+1, moviendo así el elemento pivote en la posición correcta en la matriz particionada.

Código fuente

Partition Def (arr, lb, ub):
# Se toma el último elemento de la matriz
# para ser un elemento dinámico
pivot_elt = arr [ub-1]
i = lb - 1
para j en rango (lb, ub):
# Si el elemento es menos que el elemento dinámico
Si arr [j] # Intercambia los elementos para que los elementos
# arr [lb ... yo] siempre es menos que un elemento dinámico
i = i + 1
arr [i], arr [j] = arr [j], arr [i]
# Intercambio final del elemento pivote y arr [i+1]
# para poner el elemento pivote en su lugar
arr [i+1], arr [ub-1] = arr [ub-1], arr [i+1]
Regreso i+1
Def Quick_sort (arr, lb, ub):
if (lb# Clasificar recursivamente la matriz
Q = Partition (arr, lb, ub)
arr = Quick_sort (arr, lb, q)
arr = Quick_sort (arr, q+1, ub)
regresar arr
Si __name__ == "__main__":
arr = [3, 7, 9, 2, 5, 0]
n = len (arr)
arr = Quick_sort (arr, 0, n)
Imprimir (arr)

La mejor complejidad del tiempo de QuickSort es O (n log n). En el mejor de los casos, en cada llamada al algoritmo, el algoritmo divide el problema en dos subproblemas de igual tamaño. La peor complejidad del tiempo del algoritmo de Quicksort es O (n^2). Esto ocurre cuando el elemento de partición siempre se elige como el último elemento, y la matriz ya está ordenada.