Quicksort java arraylist implementation

Question

I'm struggling with a really simple problem in java. I've implemented quicksort in java that works on arraylists and can take any value. The problem is that it works only for an arraylist lower than about 8000 size. Can anyone tell me what's wrong with my program? I think it might be connected with recursion depth limit but i'm not sure (because sometimes it works for larger sizes and sometimes not). How can I improve my quicksort implementation so it will work for much larger size of Arraylist like 100000?

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 you see anything wrong in my code, let me know so I can improve it :)

Please define *only works for ArrayLists lower than about 8000 size*. Are you getting an error?? if so, please do share — CraigR8806, Mar 17 '17 at 11:28
with high enough numbers (around 8000) your recursive calls overflow the stack limit. see this question for detailed explanation http://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack — JuniorDev, Mar 17 '17 at 11:29
That's funny because merge sort works for me perfectly , and it's also working on recursion :/ — SigKillMe, Mar 17 '17 at 11:32
If that is the error you are receiving, then @JuniorDev is absolutely right. You are over you limit of stack frames. The runtime environment retains all of the local values for each method call in something called a frame that sits on the stack. As it returns to the method and the method finishes, it releases the frame. Your only hope to retain a recursive structure would be to utilize ***Tail Recursion***. Unfortunately, with this case I believe that may be impossible. — CraigR8806, Mar 17 '17 at 11:33
In your merge sort, is your return or last statement your recursive call? — CraigR8806, Mar 17 '17 at 11:34
To be honest I have pretty much same structure when it comes to recursion like here , that's why it's so strange for me. — SigKillMe, Mar 17 '17 at 11:37
I suggest changing the way you do things in your implementation, other than recursion that is (unnecessary object creations etc.). — Shadov, Mar 17 '17 at 11:45

score 0 · Accepted Answer · edited May 23 '17 at 11:46

0

There could be many reasons why your code could not run for large number of inputs. Mostly it could be because the Heap Size capacity specified for your application is overflown. This can be resolved by increasing Heap Size of your application (check out this stackoverflow link on how to increase the heap size of your application)

edited May 23 '17 at 11:46

Community

1
1

answered Mar 17 '17 at 11:33

Vishwa Bhat

109
3

This is the wrong way to handle this problem... Increasing Heap Size should be avoided at all costs and sorting a list of 8000 elements is not something that would warrant an increase, more so an optimization – CraigR8806 Mar 17 '17 at 11:35
Not necessarily. If you have loaded huge amount of data into the memory from your application beyond specified Heap Size the your application will soon run into Out of Memory. Check this [link](https://dzone.com/articles/java-performance-tuning) on JVM Tuning, Changing JVM parameters would be one of the ways. – Vishwa Bhat Mar 17 '17 at 11:41
OP is not receiving an OOM error... This is a SO error.... This algorithm should be optimized not given a band-aid.... – CraigR8806 Mar 17 '17 at 11:43
What would you recommend to improve in my code, so I don't have to increase Heap Size and it still would run for large Arraylists? – SigKillMe Mar 17 '17 at 11:45
@SigKillMe Make the sorting logic **non-recursive** as recursion increases the stack size of the thread by repetitively adding N function definitions in the stack for N method calls. – Vishwa Bhat Mar 17 '17 at 11:54

Quicksort java arraylist implementation

1 Answers1