Quicksort Java Arraylist Implementierung

Question

Ich habe mit einem wirklich einfachen Problem in Java zu kämpfen. Ich habe Quicksort in Java implementiert, das auf Arraylisten funktioniert und jeden Wert annehmen kann. Das Problem ist, dass es nur für eine Arraylist niedriger als etwa 8000 Größe funktioniert. Kann mir jemand sagen, was mit meinem Programm nicht stimmt? Ich denke, es könnte mit Rekursion Tiefe Grenze verbunden sein, aber ich bin mir nicht sicher (denn manchmal funktioniert es für größere Größen und manchmal nicht). Wie kann ich meine Quicksort-Implementierung verbessern, so dass sie für eine größere Arraylist-Größe wie 100000 funktioniert?

import java.util.ArrayList; 
import java.util.Random; 


public class QuickSort { 
Random gener; 
int temporary,genertype,NInts,flag; 
ArrayList<Integer> mylist; 

public QuickSort(int type,int ilosc){ 
    gener = new Random(); 
    mylist= new ArrayList<>(); 
    this.genertype=type; 
    this.NInts=ilosc; 

} 

void generate(){ 
    if(genertype==0){ 
     for(int i=0;i<NInts;i++){ 
      mylist.add(gener.nextInt(100000)); 
     } 
    }else { 
     for(int i=0;i<NInts;i++){ 
      mylist.add(NInts-i); 
     } 
    } 
} 

int count1(ArrayList<Integer> list,int counter1,int counter2){ 
    while(list.get(0)<list.get(counter1)){ 

     if(counter1==counter2){ 
      flag=1; 
      return counter1; 
     } 
     counter1++; 
    } 
    flag=0; 
    return counter1; 
} 
int count2(ArrayList<Integer> list,int counter1,int counter2){ 
    while(list.get(0)>list.get(counter2)){ 
     if(counter1==counter2){ 
      flag=1; 
      return counter2; 
     } 
     counter2--; 
    } 
    flag=0; 
    return counter2; 
} 


public ArrayList<Integer> sorting(ArrayList<Integer> list) { 
    ArrayList<Integer> left = new ArrayList<Integer>(); 
    ArrayList<Integer> right = new ArrayList<Integer>(); 
    int counter1,counter2; 

    if (list.size() == 1) { 
     return list; 
    }else { 
     counter1=1; 
     counter2=list.size()-1; 

     while(counter1!=counter2) { 

      counter1=count1(list,counter1,counter2); 
      if(flag==1) 
       break; 
      counter2=count2(list,counter1,counter2); 
      if(flag==1) 
       break; 

      temporary = list.get(counter1); 
      list.set(counter1, list.get(counter2)); 
      list.set(counter2, temporary); 
     } 

     for (int i = 0; i < counter1; i++) { 
      left.add(list.get(i)); 
     } 

     for (int i = counter1; i < list.size(); i++) { 
      right.add(list.get(i)); 
     } 

     left = sorting(left); 
     right = sorting(right); 
     list=merge(left, right); 
    } 
    return list; 
} 

ArrayList<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right) { 

    if(left.get(0)>right.get(right.size()-1)){ 
    right.addAll(left); 
     return right; 
    } 
    else{ 
     left.addAll(right); 
     return left; 
    } 

} 

void printing(){ 
    for(int k=0;k<NInts;k++){ 
     System.out.print(" "+mylist.get(k)); 
    } 
} 

public static void main(String[] args){ 

    QuickSort instance = new QuickSort(1,1000); 
    instance.generate(); 
    instance.mylist=instance.sorting(instance.mylist); 
    instance.printing(); 
    } 
} 

Ps.If Sie etwas falsch in meinem Code zu sehen, lassen Sie mich wissen, damit ich es verbessern :)

Answer 1

Es gibt viele Gründe haben, warum Ihr Code nicht für große Anzahl von Eingängen laufen konnte. Meistens kann es daran liegen, dass die für Ihre Anwendung angegebene Heap-Size-Kapazität überschritten wird. Dies kann durch Erhöhen der Heap-Größe Ihrer Anwendung behoben werden (lesen Sie hierzu stackoverflow link, um die Heap-Größe Ihrer Anwendung zu erhöhen)