Python ordenación rápida
El ordenamiento rápido utiliza la estrategia de divide y vencerás (Divide and conquer) para dividir una secuencia (list) en dos subsecuencias, una más pequeña y una más grande, y luego ordenar recursivamente ambas subsecuencias.
Los pasos son:
- Selección del valor pivote: se elige un elemento de la secuencia, llamado "pivote" (pivot);
- División: se reordena la secuencia de modo que todos los elementos menores que el pivote queden antes que el pivote, y todos los elementos mayores que el pivote queden después (los elementos iguales al pivote pueden ir a cualquiera de los lados). Al finalizar esta división, la posición del pivote ya queda ordenada;
- Ordenamiento recursivo de las subsecuencias: ordenar recursivamente la subsecuencia de elementos menores que el pivote y la subsecuencia de elementos mayores que el pivote.
La condición de juicio al llegar recursivamente al nivel más bajo es que el tamaño de la secuencia sea cero o uno; en ese caso, la secuencia ya está evidentemente ordenada.
Existen varios métodos concretos para elegir el valor pivote; este método de selección tiene una influencia decisiva en el rendimiento temporal del ordenamiento.
Ejemplos
def partition(arr,low,high):
i = ( low-1 ) # Índice del elemento mínimo
pivot = arr[high]
for j in range(low , high):
# El elemento actual es menor o igual que pivot
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# arr[] --> matriz ordenada
# low --> índice inicial
# high --> índice final
# Función de ordenamiento rápido
def quickSort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Matriz ordenada:")
for i in range(n):
print ("%d" %arr[i]),
El resultado de ejecutar el código anterior es:
排序后的数组: 1 5 7 8 9 10Otras extensiones