current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite
1

Please help me optimize this bubble sort code. It's working fine otherwise.

int[] randomIntegers = {2,3,1,1,4,5,8,-2,0};
        for(int i=0;i<randomIntegers.length;i++){
            for(int j=i;j<(randomIntegers.length-1);j++){
                if(randomIntegers[i]>randomIntegers[j+1]){
                    randomIntegers[i] += randomIntegers[j+1];
                    randomIntegers[j+1] = randomIntegers[i] - randomIntegers[j+1];
                    randomIntegers[i] = randomIntegers[i] - randomIntegers[j+1];
                }
            }
        }
        for(int i:randomIntegers){
            System.out.print(i+",");
        }
share|improve this question
    
As pointed out by @Guffa, this is not bubble sort (see wikipedia, or Guffa's answer). Also it is quite odd to swap the elements by adding and subtracting bits of them; they are usually swapped using some temporary variable. –  toto2 Sep 18 '13 at 12:52
    
Here's the best implementation of bubble sort I've ever seen. It's very fast and efficient. github.com/mirrors/linux-2.6/blob/… –  Vince Panuccio Dec 5 '13 at 21:34

3 Answers 3

up vote 8 down vote accepted

If you need to optimize bubble sort, you're doing it wrong. It's not really worth optimizing something that's inherently slow. You should just use a better sorting algorithm.

share|improve this answer
2  
my sentiments exactly –  Olayinka Sep 18 '13 at 8:59
    
You feel so strongly about bubble sort that you did not even read the code. –  toto2 Sep 18 '13 at 13:11
    
True :) Doesn't really make much difference if it's a selection sort or insertion sort instead. The first step in optimizing any code is to use a better algorithm. –  Rene Saarsoo Sep 18 '13 at 13:42
up vote 7 down vote

Well, first of all, that's not bubble sort at all.

Here's bubble sort:

bool swapped = true;
while (swapped) {
  swapped = false;
  for (int i = 0; i < randomIntegers.length - 1; i++){
    if (randomIntegers[i] > randomIntegers[i + 1]) {
      swapped = true;
      int temp = randomIntegers[i];
      randomIntegers[i] = randomIntegers[i + 1];
      randomIntegers[i + 1] = temp;
    }
  }
}

Here's an improved version of bubble sort, where the items known to be sorted are excluded:

bool swapped = true;
for (int i = randomIntegers.length - 1; swapped && i >= 0; i--){
  swapped = false;
  for (int j = 0; j < i; j++){
    if (randomIntegers[j] > randomIntegers[j + 1]) {
      int temp = randomIntegers[j];
      randomIntegers[j] = randomIntegers[j + 1];
      randomIntegers[j + 1] = temp;
    }
  }
}

On the subject of optimising the code that you have, whatever algorithm that is, you can let j loop from i + 1 instead of i, so that you don't need to use j + 1 everywhere. Also, use a temporary variable to swap the items:

for (int i = 0; i < randomIntegers.length; i++) {
  for (int j = i + 1; j < randomIntegers.length; j++) {
    if (randomIntegers[i] > randomIntegers[j]) {
      int temp = randomIntegers[i];
      randomIntegers[i] = randomIntegers[j];
      randomIntegers[j] = temp;
    }
  }
}
share|improve this answer
    
Umair is using a variant of the XOR swap technique to swap values without using a local temporary variable. I could tolerate it if he actually used XOR, since it would be easier to recognize, but using the subtraction variation makes it cryptic, as evidenced by your confusion. –  200_success♦ Sep 18 '13 at 16:32
    
@200_success: Yes, I regocnise it, and I'm not confused by it. (I actually suggested a variation of it in an SQL query a few days ago.) There is just no reason to use it here, using a local variable as temporary storage is shorter and more efficient. –  Guffa Sep 18 '13 at 17:29
up vote 1 down vote

Your algorithm is nearly "selection sort" (see the wikipedia entry on sorting algorithms).

You could make it more efficient by doing the true selection sort: during the j-loop, you do not swap every time you find a value smaller than the i-value, but rather you just use the loop to find the minimal value to the right of the i-value and only after the j-loop is done do you swap, if needed.

Also, for efficiency, you should just swap the values by using a temporary variable (see Guffa's code for example) instead adding and subtracting bits of the numbers in-place.

But it would even better to implement the true bubble sort, or some inherently faster algorithm. Again, take a look at the wikipedia link.

share|improve this answer
    
+1 for doing the research to analyse what the algorithm resembles. –  Guffa Sep 19 '13 at 6:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.