[python] quicksort

[ingframin]

Qui di seguito c'e' la mia implementazione:


def quicksort(V):
l = len(V)
if l<=1:
return V

else:
ak = 0
V1 = V
V2 = V
Z = V
i1 = 0
i2 = 0
iz =0
for x in range(l):

if V[ak]>V[x]:
V1[i1]=V[x]
i1 += 1
elif V[ak]<V[x]:
V2[i2]=V[x]
i2 += 1
else:
Z[iz] = V[x]
iz += 1

A1 = quicksort(V1[0:i1])
A2 = quicksort(V2[0:i2])

return A1+Z[0:iz]+A2

1) C'e' qualcuno che riesce a renderlo piu' veloce?
2) C'e' qualcuno che sa riscriverlo iterativo e non ricorsivo?

[AnonimoVeneziano]

Ciao.

Prima di pensare alle prestazioni mi concentrerei sulla correttezza dell'algoritmo, poichè lanciando questo codice (preso paro paro dal tuo post + inizializzazioni introdotte da me):


import random

def quicksort(V):
l = len(V)
if l<=1:
return V

else:
ak = 0
V1 = V
V2 = V
Z = V
i1 = 0
i2 = 0
iz =0
for x in range(l):

if V[ak]>V[x]:
V1[i1]=V[x]
i1 += 1
elif V[ak]<V[x]:
V2[i2]=V[x]
i2 += 1
else:
Z[iz] = V[x]
iz += 1

A1 = quicksort(V1[0:i1])
A2 = quicksort(V2[0:i2])

return A1+Z[0:iz]+A2

def setit():
a = [i for i in range(0, 20)]
random.shuffle(a)
return a

a = setit()
a2 = quicksort(a)
print a2


Il risultato è simile a questo:

[2, 2, 2, 4, 4, 5, 8, 8, 8, 4, 7, 7, 7, 8, 7, 7, 9, 9, 16, 16]

[ingframin]

Ciao.

Prima di pensare alle prestazioni mi concentrerei sulla correttezza dell'algoritmo, poichè lanciando questo codice (preso paro paro dal tuo post + inizializzazioni introdotte da me):


import random

def quicksort(V):
l = len(V)
if l<=1:
return V

else:
ak = 0
V1 = V
V2 = V
Z = V
i1 = 0
i2 = 0
iz =0
for x in range(l):

if V[ak]>V[x]:
V1[i1]=V[x]
i1 += 1
elif V[ak]<V[x]:
V2[i2]=V[x]
i2 += 1
else:
Z[iz] = V[x]
iz += 1

A1 = quicksort(V1[0:i1])
A2 = quicksort(V2[0:i2])

return A1+Z[0:iz]+A2

def setit():
a = [i for i in range(0, 20)]
random.shuffle(a)
return a

a = setit()
a2 = quicksort(a)
print a2


Il risultato è simile a questo:

[2, 2, 2, 4, 4, 5, 8, 8, 8, 4, 7, 7, 7, 8, 7, 7, 9, 9, 16, 16]

Strano, mi sa che ho fatto qualche casino con le ultime modifiche, quello che avevo scritto prima funzionava... Dopo gli do un'occhiata, grazie della segnalazione :-)
EDIT:
Ho capito perché:
V1 = V
V2 = V
Z = V

Questo copia il riferimento, non il contenuto e quindi è come se ad ogni iterazione cambiassi il pivot e i vettori in base agli scambi che faccio.
Correggo e riposto

[ingframin]

def quicksort(V):
l = len(V)
if l<=1:
return V

else:
p =V[0]
V1 = [None for x in V]
V2 = [None for x in V]
Z = [p]
i1 = 0
i2 = 0
iz =0
for x in range(l):

if p>V[x]:
V1[i1]=V[x]
i1 += 1
elif p<V[x]:
V2[i2]=V[x]
i2 += 1
else:
Z.append(V[x])
iz += 1

A1 = quicksort(V1[0:i1])
A2 = quicksort(V2[0:i2])
#print(Z)
return A1[0:i1]+Z[0:iz]+A2[0:i2]

Corretto

[AnonimoVeneziano]

[CODE]

Corretto

Il tuo algoritmo fa un po' troppe copie degli array.

Ho scritto una versione in-place del quicksort che è un po' più veloce della tua:


import random
import time

def quicksort(V):
l = len(V)
if l<=1:
return V

else:
p =V[0]
V1 = [None for x in V]
V2 = [None for x in V]
Z = [p]
i1 = 0
i2 = 0
iz =0
for x in range(l):

if p>V[x]:
V1[i1]=V[x]
i1 += 1
elif p<V[x]:
V2[i2]=V[x]
i2 += 1
else:
Z.append(V[x])
iz += 1

A1 = quicksort(V1[0:i1])
A2 = quicksort(V2[0:i2])
#print(Z)
return A1[0:i1]+Z[0:iz]+A2[0:i2]

def quicksort2_true(V, start, end):
pivot = end
low_pointer = start
high_pointer = end-1

while low_pointer <= high_pointer:
while V[low_pointer] < V[pivot]:
low_pointer = low_pointer + 1
while V[high_pointer] >= V[pivot] and low_pointer <= high_pointer:
high_pointer = high_pointer - 1
if low_pointer < high_pointer:
temp = V[low_pointer]
V[low_pointer] = V[high_pointer]
V[high_pointer] = temp
low_pointer = low_pointer + 1
high_pointer = high_pointer + 1
temp = V[pivot]
V[pivot] = V[low_pointer]
V[low_pointer] = temp

if end - low_pointer > 0:
quicksort2_true(V, low_pointer, end)
if high_pointer - start > 0:
quicksort2_true(V, start, high_pointer)

def quicksort2(V):
end = len(V)-1
start = 0
if end - start > 0:
quicksort2_true(V, start, end)


def setit():
a = [i for i in range(0, 2000000)]
random.shuffle(a)
return a

a = setit()
t1 = time.clock()
a2 = quicksort(a)
t2 = time.clock()
print 'Elasped: ', t2-t1, ' s'
a = setit()
t1 = time.clock()
quicksort2(a)
t2 = time.clock()
print 'Elasped: ', t2-t1, ' s'


quicksort() è la tua, quicksort2() è la mia.

Il risultato in velocità è (per 2000000 di elementi):


MacBook-Pro-di-Marcello:~ Kariddi$ python qs2.py
Elasped: 31.817912 s <-- quicksort()
Elasped: 18.748978 s <-- quicksort2()


Ciao

[ingframin]

Era esattamente quello che volevo, sapere come andare piu' veloce :)