• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Why is my bubbleSort taking so long? Is this normal?

 
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I created a program that prints a simple list of numbers from 10 to 1. And I created a bubbleSort method to sort the numbers in ascending order. Then the program is supposed to print the sorted list. When I run it in Netbeans, I don't see any errors but it just runs for a long time. The list before sorting printed immediately. The post sorted list hasn't printed yet 20 minutes later.

Here is the code:

Can anyone tell me what is taking so long? Or why this is not working?
Thanks
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Probably because you put the value of the temporary variable in the wrong place.
 
Ray Bell
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks!
I changed it to this:
temp = myList[i + 1];
    myList[i + 1] = myList[i];
    myList[i] = temp;

It works perfectly now.
I'm still not sure how it works though.

I'm having trouble really getting the temp swap as well as the i++ versus ++i difference. If anyone has a good way of explaining this, I'd really appreciate it. Right now, I'm just blindly copying bits of code, or trying out two ways until it works....
If I ever figure all this out maybe I will write Java for REAL Dummies.
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Don't write things like
myArray[i] = temp;
in this method. Create another method in a utility class, which does that for you:-Get a sheet of paper and write an array on it. A small array will do nicely; you don't need more than 4 or 5 elements. Draw the effects of the code you had originally and the corrected code and you can see the difference much better on paper.
* * * * * * *
Everybody else gets confused about i++ so don't let it worry you. Have a look at this FAQ page and you will find a link about halfway 12‑15 lines down. Also bookmark these FAQ.
 
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ray Bell wrote:Thanks!
I changed it to this:
temp = myList[i + 1];
    myList[i + 1] = myList[i];
    myList[i] = temp;

It works perfectly now.
I'm still not sure how it works though.


Your first version didn't work because you used the wrong index in the third line of the swap. The bug was essentially restoring myList[i] to what it was before the swap thus resulting in the values not being swapped. Despite that, you still set changed to true so the loop just kept going and going. I'm surprised you waited twenty minutes for it, given that you were only sorting ten numbers. You could have waited until all the cows came in and your sort would still not have been done.

If you think that declaring the temp variable outside of the loop is saving you something, it's not. Declare variables in the smallest scope possible. Not saying this cause the problem you saw but in general, declaring variables in a scope that's wider than their actual use is an invitation for bugs. Since temp is used only inside the if-statement, that's where you should declare it. It would have been better if you had written this instead:

Or you could follow Campbell's advice and create a utility method so you'd only have to write something like: MyArrays.swap(myList, i, j)
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The swap algorithm works like this:

codetempmyList[i]myList[i + 1]
int temp = myList[i]10 ←109
myList[i] = myList[i + 1]109 ←9
myList[i + 1] = temp10910 ↩

 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . follow Campbell's advice and create a utility method so you'd only have to write something like: MyArrays.swap(myList, i, j)

I only give really good advice The utility class has the advantage that, after you have written it, you can reuse its methods for ever.
In the example Junilu gave, which is similar to what you would write on paper, he is swapping indices i and i + 1, so you could write MyArrays.swap(myList, i, i + 1)
 
I child proofed my house but they still get in. Distract them with this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic