# 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. Commented Sep 18, 2013 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/… Commented Dec 5, 2013 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 Commented Sep 18, 2013 at 8:59
• You feel so strongly about bubble sort that you did not even read the code. Commented Sep 18, 2013 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. Commented Sep 18, 2013 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. Commented Sep 18, 2013 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. Commented Sep 18, 2013 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.