It's not a secret anymore!*
The moose likes Beginning Java and the fly likes quick sort- stack overflow error? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "quick sort- stack overflow error?" Watch "quick sort- stack overflow error?" New topic
Author

quick sort- stack overflow error?

Theresa Marlin
Ranch Hand

Joined: Sep 23, 2009
Posts: 49
Hi,
I have been working on writing a java quicksort using arrays, but ran into a stack overflow error. This is one of my first projects in recursion, and I'm not sure what I'm doing wrong. Would anyone mind checking over my code? Thanks!




Thank you very much for any help you can give!!
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 30057
    
149

Theresa,
First a tip for debugging - print out the values of j and k before making the recursive call to qsort. This will show you what number it is using when it gets into the infinite sequence.

Without running it, my guess is zero. I don't see an if statement around the recursive calls. This means the code doesn't know what the base case and therefore when it should stop making recursive calls.


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19649
    
  18

Jeanne Boyarsky wrote:Without running it, my guess is zero. I don't see an if statement around the recursive calls. This means the code doesn't know what the base case and therefore when it should stop making recursive calls.

Wouldn't that be the part?

Still, you're right in j and k never changing. I've tested it with a random array and j and k never change once j hits 0.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11152
    
  16

Theresa,

I edited your post to break your comment into two lines. Our site renders a one-line comment on one line, so super-long ones tend to make it format strangely. It's usually easier to read this way, rather than having to scroll horizontally.

Just a tip for next time.

Thanks!!!


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 30057
    
149

Rob Spoor wrote:
Jeanne Boyarsky wrote:Without running it, my guess is zero. I don't see an if statement around the recursive calls. This means the code doesn't know what the base case and therefore when it should stop making recursive calls.

Wouldn't that be the part?

Still, you're right in j and k never changing. I've tested it with a random array and j and k never change once j hits 0.

Rob,
I actually missed the if statement. I tried with the array "1,2,3" and it infinitely goes on j = 0, k = 2. The interesting part is that small is length 2 and large is length 0. Small never gets smaller which means the array is never <= 1.
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 30057
    
149

Two other notes - not about your problem, but about coding in general.

1) It is traditional for classnames to use camel case and begin with a capital letter. So it would be QuickSort or at least Quicksort.
2) Your constructor ignores the array it is passed. You don't actually need to write a constructor to use instance methods. Java provides you one by default that looks like this. Or of course you could write a zero argument constructor yourself.

Theresa Marlin
Ranch Hand

Joined: Sep 23, 2009
Posts: 49
thank you, everyone, for your suggestions/ help- I will be sure to try them all out- now I at least have a general idea of what needs to be fixed
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: quick sort- stack overflow error?
 
Similar Threads
creating a list of subsets from N elements
Need help figuring out a quickSort problem
Parallel running quicksort
How do i get all subsets?
Comparing Comparable