implementazione quicksort

Question

Il seguente codice per quicksort non funziona e non riesco a capire quale sia la ragione.

#include <iostream> 
using namespace std; 
void exch(int a[],int i,int j){ 
    int s=a[i]; 
    a[i]=a[j]; 
    a[j]=s; 

} 
int partition(int a[],int l,int h); 
void quick(int a[],int l,int h){ 
    if (h<=l) return ; 
    int j=partition(a,l,h); 
    quick(a,l,j-1); 
    quick(a,j+1,h); 
    } 
int partition(int a[],int l,int h){ 
    int i=l-1; 
    int j=h; 
    int v=a[l]; 
    while(true){ 

     while(a[++i]<v); 

     while(a[--j]>v) if (j==i) break; 

      if (i>=j) break; 

     exch(a,i,j); 

    } 

    exch(a,i,h); 
    return i; 



} 
int main(){ 

    int a[]={12,43,13,5,8,10,11,9,20,17}; 
    int n=sizeof(a)/sizeof(int); 
quick(a,0,n-1); 
for (int i=0;i<n;i++){ 
    cout<<a[i]<<" "; 
} 
    return 0; 
} 

Produce

5 8 9 11 10 17 12 20 13 43 

Answer 1

nel metodo partition, che dovrebbe essere

int v = a[h]; 

e non

int v = a[l]; 

[Up Data: Ho appena testato il codice con questo cambiamento, e funziona in modo corretto, l'output:

5 8 9 10 11 12 13 17 20 43 

Answer 2

Ecco un'implementazione più chiara della fase di separazione:

def quicksort(arr, low, high): 
    if low > high or low == high: 
     return 

    pivot = randint(low, high) 
    updated_pivot = partition(pivot,arr, low, high) 
    quicksort(arr, low, updated_pivot-1) 
    quicksort(arr, updated_pivot+1, high) 


def partition(pivot, arr, low, high): 
    arr[low], arr[pivot] = arr[pivot], arr[low] #now pivot is at 'low' index of current subarray  
    start_of_ = 1 
    curr = 1 
    while curr <= high: 
     if arr[curr] <= arr[low]: 
      arr[start], arr[curr] = arr[curr], arr[start] #making sure all values between index low and index start (exclusive) are less than or equal to the pivot. 
       start+=1 
     curr += 1 

    new_pivot_location = start - 1 #the value at index start is the first value greater than the pivot (the range considered in the while loop is exclusive) 
    arr[new_pivot_location], arr[low] =arr[low], arr[new_pivot_location] 
    return new_pivot_location 

ESEMPIO RUN:

ingresso: algoritmo

[5,1,3,8, 0,2] 
    | 
    pivot 

ripartizione:

[3,1,5,8,0,2] --> after switching pivot's position 
| 
pivot 

    start 
    | 
[3,1,5,8,0,2] --> initializing start and curr 
    | 
    curr 

    start 
    | 
[3,1,5,8,0,2] --> 1 < 3, so we swap 1 & 1, and start++, curr++ 
    | 
    curr 

    start 
    | 
[3,1,5,8,0,2] --> 5 > 3, so we don't swap. Don't move start, curr++ 
     | 
     curr 

    start 
    |  
[3,1,5,8,0,2] --> 8 > 3, so we don't swap. Don't move start, curr++ 
     | 
     curr 

     start 
     | 
[3,1,0,8,5,2] --> 0 < 3, so we swap 5 and 0. start++, curr++ 
      | 
      curr 

     start 
     | 
[3,1,0,2,5,8] --> 2 < 3, so we swap 8 and 2. start++, curr++ 
      | 
      curr 

[2,1,0,3,5,8] --> swap 2 and 3, and reset pivot index. 

uscita:

[2,1,0,3,5,8] 
     | 
     pivot