Optimizing bubble sort code

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

• 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/… – Razor Dec 5 '13 at 21:34

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.

• 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

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

• 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

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.