OutOfMemoryError в реализации быстрой сортировки в Java

Question

Я пытаюсь реализовать алгоритм Quicksort, я прочитал, как это сделать с псевдокодом, и поскольку я изучаю Java (потому что я уже сделал quicksort несколько месяцев назад на C++) Я хочу внедрить его на такой язык, но при попытке запустить его, у меня возникает проблема с stackoverflow или кучей пространства, можете ли вы проверить мой код? : 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; 
} 

Спасибо за все ваши комментарии и ответы, я сделал предложенные изменения, я вставлю точное исключение:

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)

И вот модифицированный код (я перевел свои переменные, жаль, что я не заметил):

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

основная проблема связана с этой строки:

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

, который должен быть

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

Почему? Ну, первое утверждение всегда верно, и когда все разделяемые элементы равны или меньше, чем точка опоры, все они будут в мэре в том же порядке, в котором они вошли. Quicksort снова вызывается функцией который выполняет то же самое разбиение, и вы получаете бесконечный цикл. В зависимости от того, насколько велика вы создаете массивы мэра или мэра, программа выполняет ошибку при переполнении стека или ошибке памяти.

Даже если вы измените указанную выше строку, ваш вид не будет работать так, как у вас есть. Зачем? Ну, есть несколько причин. Во-первых, линия

if(menor.length>mayor.length) 

должен быть

if(j>k) 

Однако, это лишь часть проблемы. Вы не будете продолжать сортировать мэр или менор, когда они содержат все элементы, введенные в функцию. Однако, если вы отправляете их в quicksort, то вы все равно можете иметь бесконечный цикл. То, что я бы рекомендовал, заключается в том, чтобы отделить опорный элемент от остальной части массива, который вводится в quicksort (замените его первым элементом) и разделите оставшуюся часть массива. Затем установите опорный стержень между секционированным мэром и массивами регуляторов после того, как эти массивы были быстро отсортированы.

Удачи.