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

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.

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

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.