StackOverflowError pour quicksort Java

Question

Je teste un code quicksort je l'ai écrit, mais je ne sais pas pourquoi je reçois

erreur:

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.ArrayList$Itr.<init>(ArrayList.java:820) 
    at java.util.ArrayList.iterator(ArrayList.java:814) 
    at practice.Quicksort.quicksort(Quicksort.java:15) 
    at practice.Quicksort.quicksort(Quicksort.java:25) 
    at practice.Quicksort.quicksort(Quicksort.java:25) 
    at practice.Quicksort.quicksort(Quicksort.java:25) 

où la ligne 15 est:

for (int n : arr) { 

et la ligne 25 est:

more = quicksort(more); 

c ode:

public class Quicksort { 
    public static List<Integer> quicksort(List<Integer> arr) { 
     if (arr.size() <= 1) { 
      return arr; 
     } 
     List<Integer> less = new ArrayList<Integer>(); 
     List<Integer> more = new ArrayList<Integer>(); 
     int pivotIndex = arr.size()/2; 
     int pivot = arr.get(pivotIndex); 
     for (int n : arr) { 
      if (n < pivot) { 
       less.add(n); 
      } 
      else { 
       more.add(n); 
      } 
     } 
     // recursively sort 
     less = quicksort(less); 
     more = quicksort(more); 

     // concatenate all 
     less.add(pivot); 
     less.addAll(more); 
     return less; 
    } 

    public static void main(String[] args) { 
     List<Integer> test = new ArrayList<Integer>(); 
     int[] arr = {2,4,1,4,5,2,-10,3,0,33,23}; 
     for (int c : arr) { 
      test.add(c); 
     } 
     System.out.println(quicksort(test)); 
    } 
} 

Answer 1

Votre code a un défaut fondamental, ce qui augmente la possibilité que la liste nommée more soit la même dans deux itérations suivantes. Problèmes possibles se trouvent dans la section ci-dessous du code:

int pivotIndex = arr.size()/2; 
    int pivot = arr.get(pivotIndex); 
    for (int n : arr) { 
     if (n < pivot) { 
      less.add(n); 
     } 
     else { 
      more.add(n); 
     } 
    } 

Ne pas ajouter le pivot dans la liste more ou less. En outre, vous pouvez comprendre comment choisir la variante here on the blog

Answer 2

La liste more ne doit pas inclure le pivot. Si c'est le cas, le risque de more est exactement la même que celle qui a été transmise, et vous obtenez une boucle récursive infinie jusqu'à ce que le programme soit à court d'espace de pile.

Une technique courante consiste à permuter le pivot avec le premier élément de la liste, puis à créer les listes less et more à partir du second élément.