Optimizing bubble sort code

Question

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+",");
}

• toto2: 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.
• Razor: 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/…

Answer 1

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.

• Olayinka: my sentiments exactly
• toto2: You feel so strongly about bubble sort that you did not even read the code.
• Rene Saarsoo: 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.

Answer 2

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;
 }
 }
}

• 200_success: 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.
• Guffa: @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.

Answer 3

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.