programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Tim Cooke
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Paul Clapham
• Rob Spoor
• Junilu Lacar
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Piet Souris
• Carey Brown
Bartenders:

# Not running to completion

Greenhorn
Posts: 9
• Number of slices to send:
Optional 'thank-you' note:
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?

Bartender
Posts: 3225
34
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:

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?

Saloon Keeper
Posts: 9832
80
• Number of slices to send:
Optional 'thank-you' note:
Put a print statement before line 19 in qSort().

Vincent Jenkins
Greenhorn
Posts: 9
• Number of slices to send:
Optional 'thank-you' note:

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: 9832
80
• Number of slices to send:
Optional 'thank-you' note:

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.

 Consider Paul's rocket mass heater.