Win a copy of Pro Spring MVC with WebFlux: Web Development in Spring Framework 5 and Spring Boot 2 this week in the Spring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Paul Clapham
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Rob Spoor
  • Bear Bibeault
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Piet Souris
Bartenders:
  • Frits Walraven
  • Himai Minh

Not running to completion

 
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Bartender
Posts: 3225
34
IntelliJ IDE Oracle Spring Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Saloon Keeper
Posts: 8228
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 8228
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic