[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]

Originariamente inviato da 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]

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]

Originariamente inviato da ingframin

[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