Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: StackOverflowError when using quicksort

  1. #1
    Junior Member
    Join Date
    Apr 2011
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default StackOverflowError when using quicksort

    When I run the following code on a dataset of 500000 items I get a StackOverflowError. I've increased the JVM's available heap space to 512mb however I still get the same problem, I was wondering if anyone could tell me why?

    This is the code i'm using:

    package sorting2011;
     
    import java.util.Calendar;
     
    public class QuickSort implements Sorter{
     
    	@Override
    	public void sort(Comparable[] items, int cutoff) {
    		long startTime = Calendar.getInstance().getTimeInMillis();
     
    		quickSort(items, 0, items.length - 1);
     
    		long endTime = Calendar.getInstance().getTimeInMillis();
     
    		long exeTime = endTime - startTime;
    		System.out.println("Sort time: " + exeTime + " milliseconds");
    	}
     
    	public void quickSort(Comparable array[], int left, int right){
    		int i = left;
    		int k = right;
     
    		if (right - left >= 1){
    		  	Comparable pivot = array[left];
    		    Comparable tmp;
     
    		    while (k > i){
    		       	while (array[i].compareTo(pivot) != 1 && i <= right && k > i) //Stack trace says error here
    		       		i++;
     
    		       	while (array[k].compareTo(pivot) == 1 && k >= left && k >= i)
    		       		k--;
     
    		       	if (k > i){
    		       		tmp = array[i]; 
    		            array[i] = array[k];
    		            array[k] = tmp;     
    		        }
    		    }
     
    		    tmp = array[left];
    		    array[left] = array[k];
    		    array[k] = tmp;
     
    		    quickSort(array, left, k - 1);      //Stack trace says error here
    		    quickSort(array, k + 1, right);    
    		 }else{
     
    		   	return;
    	     }
    	}
     
    }

    I have indicated in the code where the stack trace says the error is coming from.

    Thanks in advance.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,237
    Thanks
    176
    Thanked 817 Times in 760 Posts
    Blog Entries
    5

    Default Re: StackOverflowError when using quicksort

    Try increasing the stack size with the argument -Xss1m.

  3. The Following User Says Thank You to copeg For This Useful Post:

    Mathew.Williams (April 22nd, 2011)

  4. #3
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: StackOverflowError when using quicksort

    1. Have you tried running your code on a smaller dataset? Does it work, or does it give you a stack overflow as well?
    2. What stack size are you using? As copeg suggested, try changing the stack size rather than the heap size.

  5. #4
    Junior Member
    Join Date
    Apr 2011
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: StackOverflowError when using quicksort

    I've solved this problem, thanks guys. I just had to increase the stack size to 2m and the heap size to 350m.

Similar Threads

  1. Quicksort algorithm displaying strange behaviour
    By Mathew.Williams in forum What's Wrong With My Code?
    Replies: 0
    Last Post: April 19th, 2011, 12:56 PM
  2. [SOLVED] StackOverflowError with recursive method
    By samfin in forum What's Wrong With My Code?
    Replies: 4
    Last Post: December 2nd, 2010, 03:05 PM
  3. Java error "java.lang.StackOverflowError"
    By sanatkumar in forum Exceptions
    Replies: 2
    Last Post: July 7th, 2009, 02:40 PM