2013-07-21 17 views
10

Ho dovuto implementare l'algoritmo QuickSort per un compito in una lingua a mia scelta e ho scelto Python.QuickSort sul posto in Python

Durante le lezioni, ci è stato detto che QuickSort è efficiente in memoria perché funziona sul posto; Ad esempio, non ha copie aggiuntive di parti dell'array di input per le ricorsioni.

Con questo in mente, ho cercato di implementare l'algoritmo QuickSort in Python, ma poco dopo ho capito che per scrivere un pezzo elegante di codice avrei dovuto passare parti della matrice alla funzione stessa mentre ricorsivo. Poichè Python crea nuove liste ogni volta che lo faccio, ho provato a usare Python3 (perché supporta la parola chiave nonlocal). Quello che segue è il mio codice commentato.

def quicksort2(array): 
# Create a local copy of array. 
arr = array 

    def sort(start, end): 
     # Base case condition 
     if not start < end: 
      return 

     # Make it known to the inner function that we will work on arr 
     # from the outer definition 
     nonlocal arr 

     i = start + 1 
     j = start + 1 

     # Choosing the pivot as the first element of the working part 
     # part of arr 
     pivot = arr[start] 

     # Start partitioning 
     while j <= end: 
      if arr[j] < pivot: 
       temp = arr[i] 
       arr[i] = arr[j] 
       arr[j] = temp 
       i += 1 
      j += 1 
     temp = arr[start] 
     arr[start] = arr[i - 1] 
     arr[i - 1] = temp 
     # End partitioning 

     # Finally recurse on both partitions 
     sort(start + 0, i - 2) 
     sort(i, end) 
    sort(0, len(array) - 1) 

Ora, non sono sicuro se ho fatto bene il lavoro o mi manca qualcosa. Ho scritto una versione più pitonica di QuickSort ma sicuramente non funziona sul posto perché continua a restituire parti della matrice di input e le concatena.

La mia domanda è, è questo il modo di farlo in Python? Ho cercato sia su Google che su SO ma non ho trovato una vera implementazione sul posto di QuickSort, quindi ho pensato che fosse meglio chiedere.

+2

Hai provato di memoria profiler Python che vi dà la linea con l'analisi memoria di linea. – Hemanth

+0

Invece di scrivere una funzione interna e usare 'nonlocale' perché non si definisce la funzione' quicksort' come 'def quicksort (array, start = 0, end = None): se end è None: end = len (array) - 1 ... '?Inoltre, è pratica comune implementare separatamente una funzione 'partition', quindi il codice quicksort diventa:' q = partition (array, start, end) quicksort (array, start, q-1) quicksort (array, q + 1 end) ' – Bakuriu

+0

È possibile passare' array' in modo ricorsivo senza copiarlo; non puoi semplicemente tagliarlo. Inoltre, non è necessario 'nonlocale' perché stai modificando solo il contenuto dell'elenco associato a' arr', non quale lista è vincolata. –

risposta

10

Non è sicuro il modo migliore, più questo famoso algoritmo avranno decine di implementazioni perfetti .. questo è mio, abbastanza facile da capire

def sub_partition(array, start, end, idx_pivot): 

    'returns the position where the pivot winds up' 

    if not (start <= idx_pivot <= end): 
     raise ValueError('idx pivot must be between start and end') 

    array[start], array[idx_pivot] = array[idx_pivot], array[start] 
    pivot = array[start] 
    i = start + 1 
    j = start + 1 

    while j <= end: 
     if array[j] <= pivot: 
      array[j], array[i] = array[i], array[j] 
      i += 1 
     j += 1 

    array[start], array[i - 1] = array[i - 1], array[start] 
    return i - 1 

def quicksort(array, start=0, end=None): 

    if end is None: 
     end = len(array) - 1 

    if end - start < 1: 
     return 

    idx_pivot = random.randint(start, end) 
    i = sub_partition(array, start, end, idx_pivot) 
    #print array, i, idx_pivot 
    quicksort(array, start, i - 1) 
    quicksort(array, i + 1, end) 

Ok prima di una funzione separata per la subroutine partizione. Prende la matrice, il punto di inizio e di fine di interesse e l'indice di pivot. Queste funzioni dovrebbero essere azzerate

Quicksort chiama quindi la subroutine della partizione per la prima volta sull'intero array; quindi chiamare in modo ricorsivo per ordinare tutto fino al pivot e dopo tutto.

chiedere se non capite qualcosa

+1

Grazie mille per questo pezzo di codice, posso vedere come è meglio del mio. Credo di aver fatto cose piuttosto stupide perché pensavo che passare la matrice alla funzione durante la ricorsione ne avrebbe fatto delle copie. –

+0

sei il benvenuto ;-) anzi, se passi un array non ne farà nessuna copia :-) – Ant

+0

Grazie per l'implementazione del partizionamento sul posto :) – seismatica

1

ho iniziato a imparare python ultimamente e ciò che segue è il mio tentativo di attuare Quicksort utilizzando python. Spero che sia utile Il feedback è benvenuto :)

#!/usr/bin/python 

Array = [ 3,7,2,8,1,6,8,9,6,9] 

def partition(a, left, right): 

    pivot = left + (right - left)/2 
    a[left],a[pivot] = a[pivot], a[left] # swap 
    pivot = left 
    left += 1 

    while right >= left : 
     while left <= right and a[left] <= a[pivot] : 
      left += 1 
     while left <= right and a[right] > a[pivot] : 
      right -= 1 

     if left <= right: 
      a[left] , a[right] = a[right], a[left] # swap 
      left += 1 
      right -= 1 
     else: 
      break 

    a[pivot], a[right] = a[right] , a[pivot] 

    return right 


def quicksort(array , left,right): 
    if left >= right: 
     return 
    if right - left == 1: 
     if array[right] < array[left]: 
      array[right], array[left] = array[left] , array[right] 
      return   

    pivot = partition(array, left, right) 

    quicksort(array, left, pivot -1) 
    quicksort(array, pivot+1,right)   

def main(): 
    quicksort(Array, 0 , len(Array) -1) 
    print Array 

main() 
0

Ecco cosa mi è venuto in mente. L'algoritmo è a posto, sembra carino ed è ricorsivo.

# `a` is the subarray we're working on 
# `p` is the start point in the subarray we're working on 
# `r` is the index of the last element of the subarray we're working on 

def part(a,p,r): 
    k=a[r] #pivot 
    j,q=p,p 
    if p<r: # if the length of the subarray is greater than 0 
     for i in range(p,r+1): 
      if a[i]<=k: 
       t=a[q] 
       a[q]=a[j] 
       a[j]=t 
       if i!=r: 
        q+=1 
       j+=1 
      else: 
       j+=1 
     part(a,p,q-1) # sort the subarray to the left of the pivot 
     part(a,q+1,r) # sort the subarray to the right of the pivot 
    return a 
def quicksort(a): 
    if len(a)>1: 
     return part(a,0,len(a)-1) 
    else: 
     return a 
0

Ecco un'altra implementazione:

def quicksort(alist): 
    if len(alist) <= 1: 
     return alist 
    return part(alist,0,len(alist)-1) 

def part(alist,start,end): 
    pivot = alist[end] 
    border = start 
    if start < end: 
     for i in range(start,end+1): 
      if alist[i] <= pivot: 
       alist[border], alist[i] = alist[i], alist[border] 
       if i != end: 
        border += 1 
     part(alist,start,border-1) 
     part(alist,border+1,end) 
    return alist 
0

Spiegazione: Pivot è sempre l'ultimo elemento dato array. Nel mio approccio tengo traccia del "confine" tra i numeri più piccoli e più grandi del pivot. Border è un indice del primo numero nel gruppo "più grande". Alla fine di ogni iterazione scambiamo il numero sotto "border" con il numero di pivot.

E il codice:

def qs(ar, start, end): 
    if (end-start < 1): 
     return 
    if (end-start == 1): 
     if(ar[start] > ar[end]): 
      tmp = ar[start] 
      ar[start] = ar[end] 
      ar[end] = tmp 
     return 
    pivot = ar[end - 1] 
    border_index = start 
    i = start 
    while(i <= end - 1): 
     if (ar[i] < pivot): 
      if i > border_index: 
       tmp = ar[i] 
       ar[i] = ar[border_index] 
       ar[border_index] = tmp 
      border_index += 1 
     i+=1 
    ar[end-1] = ar[border_index] 
    ar[border_index] = pivot 
    qs(ar, start, border_index) 
    qs(ar, border_index + 1, end) 

qs(ar, 0, n) 
Problemi correlati