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 3 of 3

Thread: Stackoverflow Recursive quicksort

  1. #1
    Member
    Join Date
    May 2011
    Posts
    61
    My Mood
    Busy
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Stackoverflow Recursive quicksort

    For my quicksort for fun I wrote, when I time it, it has no problem sorting 1000 items in order or random data of size 1000, 10K, 100K, 1M, but when it comes to applying it to 10K descending order of data, I get a stack overflow? I'm using Windows 7 64-bit core i5 Sandy bridge. I tried to set memory via > java -Xmx2g for example but it's limited and also this is for heap size to increase, not stack size which is what the quick sort I wrote is using, so should I use JVM 64-bit?

    EDIT: I just found out you can increase stack size, I'll try this first
    Last edited by IHeartProgramming; September 23rd, 2012 at 01:00 AM.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Stackoverflow Recursive quicksort

    How many times does the method call itself? Stackoveflow is usually because of runaway recursion.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Stackoverflow Recursive quicksort

    java.util.Arrays.sort() can sort an array of 10,000,000 Integers in a few seconds (on my modest 32-bit Linux workstation: Old and creaky, like me, but not as cranky as me). I just use the "out-of-the-box" default openjdk version 1.6 Java setup on my Centos 5.8 workstation; no special stack or heap enlargement.

    According to Java documentation, the Arrays.sort algorithm is "adapted from Jon L. Bentley and M. Douglas McIlroy's 'Engineering a Sort Function', Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993)."
    (From the Good Old Days at Bell Labs in Murray Hill.)

    This work is also referenced, but not elaborated on by the Wikipedia page on Quicksort.

    Here's a copy of the paper that you should be able to download: http://cs.fit.edu/~pkc/classes/writi...ngineering.pdf The methodology described in the paper is not pure quicksort,and it's not about Java, but maybe you can gain some insight by reading about how they surmounted some shortcomings of previous qsort library implementations...


    Cheers!

    Z
    Last edited by Zaphod_b; September 23rd, 2012 at 05:13 PM.

Similar Threads

  1. Quicksort
    By wholegrain in forum Java Theory & Questions
    Replies: 7
    Last Post: February 12th, 2012, 08:31 PM
  2. StackOverFlow Error
    By ankiit in forum What's Wrong With My Code?
    Replies: 3
    Last Post: January 13th, 2012, 09:49 AM
  3. Why am I getting StackOverflow errors?
    By techcom0 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: October 12th, 2011, 09:18 AM
  4. QuickSort method
    By D3158 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: June 15th, 2011, 09:17 PM
  5. StackOverflowError when using quicksort
    By Mathew.Williams in forum What's Wrong With My Code?
    Replies: 3
    Last Post: April 22nd, 2011, 05:24 PM