OutOfMemoryError dans une implémentation quicksort en Java

Question

J'essaye d'implémenter un algorithme Quicksort, j'ai lu comment le faire avec du pseudo-code et depuis que j'apprends Java (parce que j'ai déjà fait quicksort il y a quelques mois en C++) Je veux l'implémenter à un tel langage, mais je reçois un problème de stackoverflow ou d'espace de tas chaque fois que j'essaie de l'exécuter, pouvez-vous vérifier mon code? : D

public static int[] quicksort(int arreglo[]){ 
    int size=arreglo.length; 
    int pivote=arreglo[size/2]; 
    int menor[] = new int[size+2]; //If I leave the +2 I get stack overflow 
    int mayor[] = new int[size+2]; //If I delete them I get heap space problems 
    int j=0,k=0; 
    if(size>2){ 
     for(int i=0;i<size;i++){ 
      if(arreglo[i]<=pivote){ 
       menor[j]=arreglo[i]; 
       j++; 
      } 
      else{ 
       mayor[k]=arreglo[i]; 
       k++; 
      } 
     } 
     if(menor.length>=1&&mayor.length>=1) 
      return concatena(Ordena.quicksort(menor),Ordena.quicksort(mayor),j,k); 
     else 
      if(menor.length>mayor.length) 
       return menor; 
      else 
       return mayor; 
    } 
    else 
     return arreglo; 
} 

public static int[] concatena(int menor[],int mayor[],int limite1,int limite2){ 
    int completo[] = new int[limite1+limite2]; 
    System.arraycopy(menor,0,completo,0,limite1); 
    System.arraycopy(mayor,0,completo,limite1,limite2); 
    return completo; 
} 

Merci pour tous vos commentaires et vos réponses, j'ai apporté les modifications proposées, je vais coller l'exception exacte:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at Ordena.quicksort(Ordena.java:6) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21) at Ordena.quicksort(Ordena.java:21)

Et voici le code modifié (je traduis mes variables, désolé, je ne l'ai pas remarqué):

public static int[] quicksort(int array[]){ 
    int size=array.length; 
    int pivot=array[size/2]; 
    int less[] = new int[size+2]; 
    int greater[] = new int[size+2]; 
    int j=0,k=0; 
    if(size>2){ 
     for(int i=0;i<size;i++){ 
      if(array[i]<=pivot){ 
       less[j]=array[i]; 
       j++; 
      } 
      else{ 
       greater[k]=array[i]; 
       k++; 
      } 
     } 
     less[j]=pivot; 
     if(j>=1&&j>=1) 
      return concatenate(Ordena.quicksort(less),Ordena.quicksort(greater),j,k); 
     else 
      if(j>k) 
       return less; 
      else 
       return greater; 
    } 
    else 
     return array; 
} 

public static int[] concatenate(int less[],int greater[],int limit1,int limit2){ 
    int complete[] = new int[limit1+limit2]; 
    System.arraycopy(less,0,complete,0,limit1); 
    System.arraycopy(greater,0,complete,limit1,limit2); 
    return complete; 
} 

Answer 1

Le problème majeur vient de cette ligne:

if(menor.length>=1&&mayor.length>=1) 

qui devrait être

if(j>=1&&k>=1) 

Pourquoi? Eh bien, la première déclaration est toujours vraie, et quand tous les éléments partitionnés sont égaux ou inférieurs au pivot, ils seront tous dans le même ordre que celui dans lequel ils sont entrés. Quicksort est appelé à nouveau sur la fonction qui fait exactement le même partitionnement et vous obtenez une boucle infinie. En fonction de la taille des tableaux menor ou mayor, le programme commet une erreur sur un débordement de pile ou une erreur de mémoire en premier.

Même si vous modifiez la ligne ci-dessus, votre tri ne fonctionnera pas comme vous l'avez. Pourquoi? Eh bien, il y a plusieurs raisons. Tout d'abord, la ligne

if(menor.length>mayor.length) 

devrait être

if(j>k) 

Cependant, c'est seulement une partie du problème. Vous ne continuerez pas à trier le maire ou le menor lorsqu'ils contiennent tous les éléments entrés dans la fonction. Cependant, si vous les envoyez sur quicksort, vous pouvez toujours avoir une boucle infinie. Ce que je recommande est de séparer le pivot du reste du tableau qui est entré dans quicksort (l'échanger avec le premier élément par exemple) et de partitionner le reste du tableau. Ensuite, mettez le pivot en place entre le maire partitionné et les tableaux menor après que ces tableaux ont été eux-mêmes quicksorted.

Bonne chance.