Quicksort Python

Aplicación de Quicksort en Python

1. La elección del pivote
2. La función de partición
3. La implementación recursiva

def quicksort(arr): if len(arr) <= 1: return arr pivot = arr.pop() lesser = [] greater = [] for x in arr: if x <= pivot: lesser.append(x) else: greater.append(x) return quicksort(lesser) + [pivot] + quicksort(greater)

Flujo de trabajo del algoritmo Quicksort de Python

1. Elige un elemento pivote de la lista.
2. Divide la lista alrededor del pivote, de forma que los elementos menores que el pivote se coloquen antes del pivote, y los mayores que el pivote se coloquen después del pivote.
3. Aplica recursivamente el algoritmo Quicksort en las dos submatrices (elementos menores que el pivote y elementos mayores que el pivote) hasta que todas las matrices estén ordenadas.

Implementación de Quicksort en Python: Ejemplos

• Seleccionar un pivote adecuado es crucial para la eficacia del algoritmo. Algunas estrategias comunes son seleccionar el primer elemento, el del medio o el último, o utilizar la mediana de tres elementos (primero, medio y último).

• A continuación, reorganiza la matriz de modo que los elementos menores que el pivote se coloquen antes de él y los mayores que él, después. Este paso se suele llamar "particionar".

• Por último, aplica recursivamente el algoritmo Quicksort en las dos submatrices (elementos menores que el pivote y elementos mayores que el pivote) hasta llegar al caso base (una matriz vacía o una matriz de tamaño 1).

def quicksort(arr): if len(arr) <= 1: return arr pivot = arr.pop() lesser = [] greater = [] for x in arr: if x <= pivot: lesser.append(x) else: greater.append(x) return quicksort(lesser) + [pivot] + quicksort(greater)

Implementación en Python de la ordenación rápida in situ

• De forma similar a la implementación anterior, selecciona un pivote apropiado.

• Crea una función de partición que tome la matriz, un índice inicial y un índice final como argumentos de entrada. Esta función reordenará los elementos alrededor del pivote y devolverá el índice de la nueva ubicación del pivote.

• Define la función que toma una matriz, un índice inicial y un índice final como argumentos de entrada. Esta función realizará la ordenación rápida en el lugar llamando a la función de partición y ordenando recursivamente las submatrices.

:def partition(arr, low, high): pivot_idx = (low + high) // 2 arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] pivot = arr[high] i = low - 1 for j in range(low, high):
      si arr[j] < pivote: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[alto] = arr[alto], arr[i + 1] return i + 1 def quicksort_inplace(arr, bajo, alto): if bajo < alto:
      pivot_index = partition(arr, low, high) quicksort_inplace(arr, low, pivot_index - 1) quicksort_inplace(arr, pivot_index + 1, high)

arr = [10, 3, 8, 4, 2] quicksort_inplace(arr, 0, len(arr) - 1)

Técnicas Avanzadas de Ordenación Rápida

1. Crea una pila para llevar la cuenta de los índices de los elementos a ordenar.
2. Mientras la pila no esté vacía, extrae los dos elementos superiores (que representan los límites inferior y superior de la submatriz) de la pila.
3. Divide la submatriz y obtén el índice de la nueva ubicación del pivote.
4. Introduce los índices de las submatrices izquierda y derecha en la pila para seguir particionando y ordenando.

def partición(arr, bajo, alto): pivot_idx = (bajo + alto) // 2 arr[pivot_idx], arr[alto] = arr[alto], arr[pivot_idx] pivot = arr[alto] i = bajo - 1 for j in rango(bajo, alto): if arr[j] < pivot:
          i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 def quicksort_iterative(arr): stack = [(0, len(arr) - 1)] while stack: low, high = stack.pop() if low < high: pivot_index = partition(arr, low, high) stack.append((low, pivot_index - 1)) stack.append((pivot_index + 1, high)

Optimizar el algoritmo de ordenación rápida de Python

• Pivote aleatorio: Selecciona un elemento aleatorio de la lista como pivote. Esto introduce aleatoriedad en el algoritmo, lo que puede ayudar a evitar los peores casos.
• Mediana de tres: Elige la mediana de los elementos primero, medio y último de la lista como pivote. Este enfoque tiende a mejorar la eficacia de la partición, por lo que acelera el algoritmo.

• Utilizar un enfoque híbrido en el que cambies a un algoritmo de ordenación más sencillo (por ejemplo, Ordenación por Inserción) para submatrices pequeñas puede evitar llamadas recursivas excesivas y mejorar el rendimiento general.

• Otra técnica de optimización del rendimiento es paralelizar el algoritmo dividiendo la lista en partes más pequeñas y ordenando cada parte simultáneamente utilizando varias unidades de procesamiento o subprocesos.

• Identificando la submatriz mayor y menor tras la partición, puedes eliminar una de las llamadas recursivas ordenando primero la submatriz menor. Esto reduce el número de llamadas a funciones y la sobrecarga asociada.