Tu implementación de quicksort funciona ordenado la lista 'in-place', sin usar memoria adicional, ese no es el problema.
Tienes algunos errores:
Deberias hacer casting a int
al cargar los datos en la lista:
arreglo.append(int(linea.strip())
De lo contrario, quicksort
ordenará una lista de cadenas (orden lexicográfico) y no una de enteros.
Hay errores de identación en la función leerLista
, además hay dos input
que no usas para nada. Debería ser algo así:
def leeLista():
arreglo=[]
arch = open('or.txt', 'r')
for linea in arch:
arreglo.append(int(linea.strip()))
arch.close()
return arreglo
No importas time
Por otro lado hay cosas que se pueden mejorar para hacer el código más efiiente y 'pythónico':
No uses el índices para imprimir la lista, esto es ineficiente. En su lugar itera sobre la lista con el for:
def imprimeLista(arreglo):
for n in arreglo:
print n
El método append
de las listas es lento, sería mucho más simple y eficiente usar compresión de listas para generar la lista a partir del txt:
def leeLista():
with open('quicksort_datos.txt', 'r') as f:
return [int(linea.strip()) for linea in f]
El código podría quedar así:
from time import time
def quick_sort(arreglo, izq, der):
i = izq
j = der
piv = arreglo[(izq + der) // 2]
while i <= j:
while arreglo[i] < piv and j <= der:
i += 1
while piv < arreglo[j] and j > izq:
j -= 1
if i <= j:
arreglo[i], arreglo[j] = arreglo[j], arreglo[i]
i += 1
j -= 1
if izq < j:
quick_sort(arreglo, izq, j)
if i < der:
quick_sort(arreglo, i, der)
def imprimir_lista(arreglo):
for n in arreglo:
print(n)
def leer_lista(ruta):
with open(ruta, 'r') as f:
return [int(linea.strip()) for linea in f]
if __name__ == "__main__":
a = leer_lista('quicksort_datos.txt')
tiempo_inicial = time()
quick_sort(a, 0, len(a)-1)
tiempo_final = time()
tiempo_ejecucion = tiempo_final - tiempo_inicial
print('El tiempo de ejecucion fue de {} segundos.'.format(tiempo_ejecucion))
imprimir_lista(a)
Algo muy importante y que no has aclarado es cómo está estructurado tu txt. El código que usas es para leer archivos de la forma:
2
24
3
26
21
1
...
Es decir, cada elemento está en una línea diferente.
Decir que aunque tu implementación de QuickSort es correcta, es bastante ineficiente, la verdadera clave del algoritmo está en hacer la partición del array en torno al pivote lo más eficiente posible. Otra posible implementación puede ser:
def quick_sort_2(array, left, right):
'''Quick Sort recursiva con partición, ordenamiento in-place'''
if right <= left:
return None
new_right = left
new_left = right
idx = left + 1
pivot = array[left]
# Particion
while idx <= new_left:
if array[idx] < pivot:
array[new_right], array[idx] = array[idx], array[new_right]
new_right += 1
idx += 1
elif array[idx] > pivot:
array[new_left], array[idx] = array[idx], array[new_left]
new_left -= 1
else:
idx += 1
quick_sort_2(array, left, new_right - 1)
quick_sort_2(array, new_left + 1, right)
Un pequeño test con un array aleatorio de 4000 enteros:
In [17]: array = [random.randint(-1000, 1000) for _ in range(4000)]
array2 = array.copy()
In [18]: array
Out[18]: [930,
17,
378,
-799,
-853,
-686,
-768,
In [19]: %time quick_sort(array, 0, len(array)-1)
CPU times: user 1min 34s, sys: 13.3 ms, total: 1min 34s
Wall time: 1min 34s
In [20]: %time quick_sort_2(array2, 0, len(array2)-1)
CPU times: user 11.3 ms, sys: 0 ns, total: 11.3 ms
Wall time: 10.7 ms
In [21]: array
Out[21]: [-1000,
-1000,
-1000,
-999,
-998,
` -997,
-997,
-996,
...]
In [22]: array == array2
Out[22]: True
Pasamos de un minuto y medio a unos 10 milisegundos....
Importante: El algoritmo anterior es un claro ejemplo de recursión y del paradigma "divide y vencerás". No obstante, la recursión tiene como límite el tamaño de la pila. Python por defecto tiene un límite de 1000 llamadas recursivas, esto es así para proteger la pila de C ya que su desbordamiento implica la terminación del propio intérprete. Esto hace que el algoritmo no sea adecuado para iterables muy extensos (aunque depende de los elementos y el orden de partida ya que esto determina el número de particiones)
Edición:
En relación a algunos comentarios sobre que el código original no es compatible con Python 3, he editado el código para que si lo sea. El problema estaba en la línea:
piv = arreglo[(izq + der) / 2]
La causa es que en Python 2 el tipo del resultado de la división depende del de los operandos. Si ambos son enteros se retorna un entero (división entera), si alguno es un float se retorna un float (división real). En Python 3 el operador /
siempre retorna un float con la división real. Como no está permitido usar float para indexar tenemos un error, la solución es simplemente usar el operador de la división entera //
:
piv = arreglo[(izq + der) // 2]