• Post Reply Bookmark Topic Watch Topic
  • New Topic

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

 
Ray Bell
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • 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
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Probably because you put the value of the temporary variable in the wrong place.
 
Ray Bell
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • 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.
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • 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.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • 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: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • 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: 56599
172
  • Mark post as helpful
  • send pies
  • 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)
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!