Stackoverflow z implementacją Java Quicksort

Question

Masz problemy z implementacją quicksort w Javie. Dostaję błąd stackoverflow, gdy uruchamiam ten program i nie jestem do końca pewien dlaczego. Jeśli ktokolwiek może wskazać błąd, byłoby wspaniale.

si jest początkowym indeksem. ei jest końcowym indeksem.

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

Najpierw należy ustalić granice w qsort rekurencyjnego wywołania sugerowane przez Keitha, gdyż w przeciwnym razie jesteś zawsze sortowania cały wachlarz kółko jeszcze raz. Musisz dopasować swoją pętlę partycji: j jest indeksem, od początku subarrayu do końca (włączając ostatni element). Musisz więc zapętlić od si + 1 do ei (w tym ei).

To jest poprawiony kod. Przeprowadziłem kilka przypadków testowych i wydaje się, że wszystko dobrze.

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

Być może na dłoniach masz nieokreślony błąd rekursji. Nie jestem pewien z mojego szybkiego skanowania, ale ...

Nawet jeśli nie, nadal będziesz używać partii stosu z tą implementacją. Wystarczająco, aby spowodować przepełnienie stosu. Co się stanie, jeśli nazwiesz go milionem pozycji, które są już posortowane? Podzielisz je na 1 i 999,999 pozycji, a następnie rekurencyjnie. Potrzebujesz 1 miliona klatek stosu, aby to działało.

Istnieje wiele sposobów na rozwiązanie tego problemu, w tym rekursowanie na mniejszych z dwóch zakresów i iterowanie na większej z dwóch lub wdrażanie samego stosu w strukturze sterty itd. Prawdopodobnie chcesz zrobić jeszcze lepiej to jednak, ponieważ głęboki stos oznacza również, że minąłeś z sortowaniem O (n lg n).

p.s. błąd jest tutaj:

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

powinny być

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

Answer 3

Można spróbować to:

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; 
    } 

Źródło: 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); 
    } 
} 

Spróbuj tego. To zadziała na pewno.

Answer 5

// Wystarczy realizowane klasy tester do tego i będzie działać

public int [] sort (int [] A, int, int z) {

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; 

}

Int publicznego przegroda (Int A [], Int z, int) {

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 nieznacznie wrażliwe na wkład, zdarza być we właściwej kolejności, w takim przypadku może pominąć niektóre swapy. Mergesort nie posiada żadnych takich optymalizacji, co sprawia, że ​​Quicksort jest nieco szybszy w porównaniu do 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]); 
}