Stackoverflow con implementazione Quicksort Java

Question

Avendo alcuni problemi nell'implementazione di quicksort in java. Ottengo un errore StackOverflow quando eseguo questo programma e non sono esattamente sicuro del perché. Se qualcuno può segnalare l'errore, sarebbe fantastico.

si è l'indice di partenza. ei è l'indice finale.

public static void qsort(int[] a, int si, int ei){ 

    //base case 
    if(ei<=si || si>=ei){} 


    else{ 
     int pivot = a[si]; 
     int length = ei - si + 1; 
     int i = si+1; int tmp; 

     //partition array 
     for(int j = si+1; j<length; j++){ 
      if(pivot > a[j]){ 
       tmp = a[j]; 
       a[j] = a[i]; 
       a[i] = tmp; 

       i++; 
      } 
     } 

     //put pivot in right position 
     a[si] = a[i-1]; 
     a[i-1] = pivot; 

     //call qsort on right and left sides of pivot 
     qsort(a, 0, i-2); 
     qsort(a, i, a.length-1); 
    } 
} 

Answer 1

primo luogo si dovrebbe fissare i limiti della chiamata ricorsiva qsort come suggerito da Keith, dal momento che altrimenti sei sempre l'ordinamento l'intero array più e più volte ancora. È necessario regolare il ciclo della partizione: j è un indice, che va dall'inizio del subarray alla fine di esso (incluso l'ultimo elemento). Quindi è necessario passare da si + 1 a ei (compresi ei).

Quindi questo è il codice corretto. Ho eseguito alcuni test case e sembra che stia andando bene.

public static void qsort(int[] a, int si, int ei){ 
    //base case 
    if(ei<=si || si>=ei){} 

    else{ 
     int pivot = a[si]; 
     int i = si+1; int tmp; 

     //partition array 
     for(int j = si+1; j<= ei; j++){ 
      if(pivot > a[j]){ 
       tmp = a[j]; 
       a[j] = a[i]; 
       a[i] = tmp; 

       i++; 
      } 
     } 

     //put pivot in right position 
     a[si] = a[i-1]; 
     a[i-1] = pivot; 

     //call qsort on right and left sides of pivot 
     qsort(a, si, i-2); 
     qsort(a, i, ei); 
    } 
} 

Answer 2

Si potrebbe avere un bug di ricorsione illimitato sulle vostre mani. Non sono sicuro dalla mia scansione veloce, ma ...

Anche se non lo fai, stai ancora utilizzando lotti di stack con questa implementazione. Abbastanza per causare un overflow dello stack. Cosa succede se lo chiami con 1 milione di articoli già ordinati? Dividerli in 1 e 999.999 elementi, quindi ricorri. Quindi avrai bisogno di 1 milione di frame stack per far funzionare tutto questo.

Ci sono molti modi per risolvere questo problema, tra cui la ricorsione sul più piccolo dei due intervalli e l'iterazione sul più grande dei due, o l'implementazione dello stack da soli in una struttura dati dell'heap, ecc. Probabilmente vuoi fare ancora meglio tuttavia, poiché lo stack profondo significa anche che stai superando il limite di ordinamento O (n lg n).

p.s. il bug è qui:

qsort(a, 0, i-2); 
qsort(a, i, a.length-1); 

dovrebbe essere

qsort(a, si, i-2); 
qsort(a, i, ei); 

Answer 3

Si può provare questo:

public void sort(int[] A) { 
     if (A == null || A.length == 0) 
      return; 
     quicksort(A, 0, A.length - 1); 
    } 

    public void quicksort(int[] A, int left, int right) { 
     int pivot = A[left + (right - left)/2]; 
     int i = left; 
     int j = right; 
     while (i <= j) { 
      while (A[i] < pivot) { 
       i++; 
      } 
      while (A[j] > pivot) { 
       j--; 
      } 
      if (i <= j) { 
       exchange(i, j); 
       i++; 
       j--; 
      } 
     } 

     if(left < j) 
      quicksort(A,left,j); 
     if(i < right) 
      quicksort(A,i,right); 
    } 

    public void exchange(int i, int j){ 
     int temp=A[i]; 
     A[i]=A[j]; 
     A[j]=temp; 
    } 

    public String toString() { 
     String s = ""; 
     s += "[" + A[0]; 
     for (int i = 1; i < A.length; i++) { 
      s += ", " + A[i]; 
     } 
     s += "]"; 
     return s; 
    } 

Fonte: Code 2 Learn: Quick Sort Algorithm Tutorial

Answer 4

import java.util.Arrays; 


public class QuickSort { 


    public static int pivot(int[] a, int lo, int hi){ 
     int mid = (lo+hi)/2; 
     int pivot = a[lo] + a[hi] + a[mid] - Math.min(Math.min(a[lo], a[hi]), a[mid]) - Math.max(Math.max(a[lo], a[hi]), a[mid]); 

     if(pivot == a[lo]) 
      return lo; 
     else if(pivot == a[hi]) 
      return hi; 
     return mid; 
    } 

    public static int partition(int[] a, int lo, int hi){ 

     int k = pivot(a, lo, hi); 
     //System.out.println(k); 
     swap(a, lo, k); 
     //System.out.println(a); 
     int j = hi + 1; 
     int i = lo; 
     while(true){ 

      while(a[lo] < a[--j]) 
       if(j==lo) break; 

      while(a[++i] < a[lo]) 
       if(i==hi) break; 

      if(i >= j) break; 
      swap(a, i, j); 
     } 
     swap(a, lo, j); 
     return j; 
    } 

    public static void sort(int[] a, int lo, int hi){ 
     if(hi<=lo) return; 
     int p = partition(a, lo, hi); 
     sort(a, lo, p-1); 
     sort(a, p+1, hi); 
    } 

    public static void swap(int[] a, int b, int c){ 
     int swap = a[b]; 
     a[b] = a[c]; 
     a[c] = swap; 
    } 

    public static void sort(int[] a){ 
     sort(a, 0, a.length - 1); 
     System.out.print(Arrays.toString(a)); 
    } 

    public static void main(String[] args) { 
     int[] arr = {5,8,6,4,2,9,7,5,9,4,7,6,2,8,7,5,6}; 
     sort(arr); 
    } 
} 

Prova questa. Funzionerà di sicuro.

Answer 5

// appena implementato la classe tester per questo e funzionerà

public int [] sort (int [] A, int da, int a) {

if(from<to){ 
    int pivot=partition(A,from,to); 
    if(pivot>1) 
     sort(A,from, pivot-1); 

    if(pivot+1<to) 
     sort(A, pivot+1, to); 


} 

return array; 

}

public int partizione (int a [], int da, int a) {

while(from < to){ 
    int pivot=A[from]; 

    while(A[from]<pivot) 
     from++; 

    while(A[to]>pivot) 
     to--; 


    if(from<to) 
     swap(A,to,from); 



} 
    return to; 
} 

private void swap(int A[], int i, int j){ 
    int temp = A[i]; 
    A[i] = A[j]; 
    A[j] = temp;} 

Answer 6

Quicksort è leggermente sensibile a input che succede essere nel giusto ordine, nel qual caso può saltare alcuni swap. Mergesort non ha tali ottimizzazioni, il che rende Quicksort un po 'più veloce rispetto a Mergesort.

Why Quick sort is better than Merge sort

Answer 7

int partition(int array[], int too_big_index, int too_small_index) 
{ 
    int x = array[too_big_index]; 
    int i = too_big_index; 
    int j = too_small_index; 
    int temp; 
    do 
    {     
     while (x <array[j]) 
     { 
       j --; 
     } 
     while (x >array[i]) 
     { 
       i++; 
     } 
      if (i < j) 
     { 
       temp = array[i];  
       array[i] = array[j]; 
       array[j] = temp; 
     } 
    }while (i < j);  
    return j;   // middle 
} 

void QuickSort(int num[], int too_big_index, int too_small_index) 
{ 
     // too_big_index = beginning of array 
     // too_small_index = end of array 

    int middle; 
    if (too_big_index < too_small_index) 
    { 
      middle = partition(num, too_big_index, too_small_index); 
      QuickSort(num, too_big_index, middle); // sort first section 
      QuickSort(num, middle+1, too_small_index); // sort second section 
    } 
    return; 
} 



void main() 
{ 
    int arr[]={8,7,13,2,5,19,1,40,12,34}; 

    QuickSort(arr,0,9); 
    for(int i=0;i<10;i++) 
     System.out.println(arr[i]); 
}