Stackoverflow error in my quicksort implementation

Question

I have extended my codes with having an additional insertion sort algorithm to be chosen by giving the boolean value insertionSort either true or false when constructing a class instance. But when I execute my codes, then i get Stackoverflow error. The codes are as follows:

    import java.util.Random;

    /**
     * Write a description of class QuickSort1 here.
     * 
     * @author (your name) 
     * @version (a version number or a date)
     */
    public class QuickSort1 implements IntSorter
    {
        private int[] v;
        private Random randomGenerator;
        private boolean insertionSort;
        private InsertionSort insertionSorter;

        public QuickSort1(boolean useInsertionSort)
        {
            randomGenerator = new Random();
            insertionSort = useInsertionSort;
            if(insertionSort)
                insertionSorter = new InsertionSort();
        }

        public void sort(int[] v)
        {
            this.v = v;
            if(this.v.length > 0) {
                quickSort(this.v, 0, this.v.length-1);
            }
            else {
                return;
            }
        }

        private void quickSort(int[] v, int first, int last)
        {
            final int startInsertion = 20;
            int First = first;
            int Last = last;
            int pivot = v[randomGenerator.nextInt(v.length)];        

            if(Last-First<2 && !insertionSort)
                return;
            else if(insertionSort) {
                if(pivot >= Last-startInsertion)
                    v = insertionSorter.sort(v);
            }
            else {
                while(First <= Last) {
                    while(v[First] < pivot) {
                        First++;
                    }
                    while(v[Last] > pivot) {
                        Last--;
                        if(Last==0)
                            break;
                    }
                    if(First<=Last) {
                        int temp = v[First];
                        v[First] = v[Last];
                        v[Last] = temp;
                        First++;
                        Last--;
                    }
                }

                if(first < Last

)
                quickSort(v, first, Last);
            if(First < last)
                quickSort(v, First, last);
        }        
    }

    public boolean getInfo()
    {
        return insertionSort;
    }
}

For the alternative insertion algorithm I have implemented a simple class with the following codes:

/**
 * Write a description of class InsertionSort here.
 * 
 * @author (your name) 
 * @version (a version number or a date)
 */
public class InsertionSort
{
    int[] v;

    /**
     * Constructor for objects of class InsertionSort
     */
    public InsertionSort()
    {
    }

    public int[] sort(int[] v)
    {
        for(int i=1;i<v.length;i++) {
            int temp = v[i];
            int j;
            for(j=i-1;j>=0 && temp<v[j];j--) {
                v[j+1] = v[j];
            }
            v[j+1] = temp;
        }
        return v;
    }
}

The error messages I now get for executing this algorithm for arrays with the size of 10.000-100.000 elements are the following:

java.lang.StackOverflowError
    at java.util.Random.nextInt(Random.java:307)
    at QuickSort1.quickSort(QuickSort1.java:40)
    at QuickSort1.quickSort(QuickSort1.java:68)

The error at line 68 gets reapeted in the terminal a lot of times and it indicates on the first recursive call of the quickSort method. The line 40 indicates on the line where the pivot element gets decided by Java's randomizing int generator.

I have a strong feeling that this algorithm perhaps cannot be better than it is now since for bigger number of elements, the stack will get empty during the execution for great numbers of elements to be sorted and therefore I perhaps get that StackOverflowError. But perhaps you have another opinion about this problem?

Thanks in advance for helping me out with this :D

I strongly recommend you step through this with a debugger. You'll be able to see immediately what's going on. — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Feb 26, 2015 at 18:05
@timrau: you're right, it should be more better choices of name on the variables :D — user2566415
– user2566415, Commented Feb 26, 2015 at 18:09
@David Wallace: I had, but it just keeps going and going, I can't advance further than just seeing repetition of the method call. And I mean that this algorithm is supposed to be able to sort maximally 100.000 elements, then the debugger will not fit that good anylonger for searching the problem. For few elements, then the implementation works well. — user2566415
– user2566415, Commented Feb 26, 2015 at 18:12
Your quicksort is working fine without the InsertionSort. I think you should just increase your heap size. For what is the InsertionSort? — Andy_Lima
– Andy_Lima, Commented Feb 26, 2015 at 19:31

Community · Accepted Answer · 2017-05-23 11:43:23Z

0

So here we go. I tried your code with a array size of 1,000,000, there 2GB RAM where not enough. So finally the answer will not be satisfying for you, but to point that problem out could be a nightlong program. But I think Stefan Mandel striked the nerve, so if you are interested, feel free to investigate in this direction. But now I won't let you go like that. I did your homework. This is working even with the regular heap size. Here is a example how to increase the heap. You'll only need the -Xmx1024 to increase the RAM to 1 GB.

public class QuickFooBar {

public static void main(String[] args) {
    Random random = new Random();
    int[] arr = new int[1000000];
    for (int i = 0; i < arr.length; ++i) {
        arr[i] = random.nextInt(1000000);
    }

    QuickSort1 test;
    test = new QuickSort1(false);
    test.setV(arr);
    test.quickSort(0, arr.length - 1);
    arr = test.getV();

    for (int i = 0; i < arr.length; ++i) {
        System.out.println(arr[i] + ", ");
    }
}

}

public class QuickSort1 {

private int[] arr;
private final boolean insertionSort;


public QuickSort1(final boolean insertionSort) {
    this.insertionSort = insertionSort;
}

public void quickSort(int left, int right) {
    final int startInsertion = 20;
    if (insertionSort) {
        if (((left + right) / 2) >= right - startInsertion) {
            arr = new InsertionSort().sort(arr);
            return;
        }
    }
    int index = partition(left, right);
    if (left < index - 1) {
        quickSort(left, index - 1);
    }
    if (index < right) {
        quickSort(index, right);
    }
}

private int partition(int left, int right) {
    int i = left, j = right;
    int tmp;
    int pivot = arr[new Random(right).nextInt()];
    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };
    return i;
}

public boolean getInfo() {
    return insertionSort;
}

public int[] getV() {
    return arr;
}

public void setV(int[] v) {
    this.arr = v;
}

}

public class InsertionSort {

public int[] sort(int[] v) {
    for (int i = 1; i < v.length; ++i) {
        int temp = v[i];
        int j;
        for (j = i - 1; j >= 0 && temp < v[j]; j--) {
            v[j + 1] = v[j];
        }
        v[j + 1] = temp;
    }
    return v;
}

}

    public int[] sort(int[] v) {
    for (int i = 1; i < v.length; ++i) {
        int temp = v[i];
        int j;
        for (j = i - 1; j >= 0 && temp < v[j]; j--) {
            v[j + 1] = v[j];
        }
        v[j + 1] = temp;
    }
    return v;
}

}

edited May 23, 2017 at 11:43

CommunityBot

11 silver badge

answered Feb 26, 2015 at 20:48

Andy_Lima

15913 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user2566415 Over a year ago

I really appreciate the work you have done and for your time effort, but your solution does not contain a pivot element that is randomly chosen from the first point to last in an array. And I don't know, I might have solved on my hand by changing int pivot = v[randomGenerator.nextInt(Last-First+1)+First]; and since then, I haven't got any errors with my program nor stackoverflows. But do you think it is enough?

Andy_Lima Over a year ago

Do you know know for what the seed in the random is? Anyways now you get a random pivot.

user2566415 Over a year ago

Well, you could if you have time develop the question about the random seed. I am not so put in when it comes to the random class structure etc. But isn't that the point, with having a pivot element that is randomly?

Andy_Lima Over a year ago

And sorry it's not said that it needs to increase calculating time but it could. If you want to give it a shot what is faster, the random or the center version let me know the result!

Collectives™ on Stack Overflow

Stackoverflow error in my quicksort implementation

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related