• Post Reply Bookmark Topic Watch Topic
  • New Topic

Not running to completion  RSS feed

 
Vincent Jenkins
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm having an issue with quicksort

Here is my main program code



And here is the qsort implementation



Also here is the Car class just for sake of completeness



The implementation will not accept the tests when using input sizes of 100, 200, 300, etc to 1000 but when I change it to 10, 20, 30, to 100 it works just fine. The 100 - 1000 example will only run like 5 runs before it stops, making it to about 500 input size. Is this just a problem with the recursive nature of qsort mixed with a user defined class or is this a problem with my actual code? Would it solve the problem to change it to an array of integers instead?
 
Mohamed Sanaulla
Bartender
Posts: 3185
34
Google App Engine Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I guess its taking time to complete. May be you need to debug to see if its going into the algorithmic implementation. Also Quicksort takes O(n^2) time in its worst case and O(nlogn) in its average case. So you can calculate approximate time taken for the sorting based on input size - n
 
Vincent Jenkins
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mohamed Sanaulla wrote:I guess its taking time to complete. May be you need to debug to see if its going into the algorithmic implementation. Also Quicksort takes O(n^2) time in its worst case and O(nlogn) in its average case. So you can calculate approximate time taken for the sorting based on input size - n


Is it really just a matter of time? I feel like there's more issues because my CPU usage increases to nearly 100% on run. Unfortunately I have to come up with the counts for each of the types of operations so that I can graph it on a chart for class
 
Vincent Jenkins
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vincent Jenkins wrote:
Mohamed Sanaulla wrote:I guess its taking time to complete. May be you need to debug to see if its going into the algorithmic implementation. Also Quicksort takes O(n^2) time in its worst case and O(nlogn) in its average case. So you can calculate approximate time taken for the sorting based on input size - n


Is it really just a matter of time? I feel like there's more issues because my CPU usage increases to nearly 100% on run. Unfortunately I have to come up with the counts for each of the types of operations so that I can graph it on a chart for class


Ya... As I let it go nothing else happens. It just stays there forever. If I run it, it will run to like run 5 instantly and just stop. Then the next run it'll get to 7 and hang. Then 4. Then 8. It's just random where it stops. I feel as if there's a case that's forcing it to recurse forever but then that wouldn't make sense because wouldn't the stack overflow? If that's the case how would I see that it's overflowing?
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Put a print statement before line 19 in qSort().
 
Vincent Jenkins
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:Put a print statement before line 19 in qSort().


Did that and it generates about 60 prints before it stops after Run #1
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vincent Jenkins wrote:
Carey Brown wrote:Put a print statement before line 19 in qSort().


Did that and it generates about 60 prints before it stops after Run #1



It all depends on the random data values - run it over and over until you see it hang.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!