1
\$\begingroup\$

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+",");
}
Improve this question
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – toto2 Sep 18 '13 at 12:52
  • \$\begingroup\$ 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/… \$\endgroup\$ – Razor Dec 5 '13 at 21:34
12
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
  • 3
    \$\begingroup\$ my sentiments exactly \$\endgroup\$ – Olayinka Sep 18 '13 at 8:59
  • 2
    \$\begingroup\$ You feel so strongly about bubble sort that you did not even read the code. \$\endgroup\$ – toto2 Sep 18 '13 at 13:11
  • \$\begingroup\$ 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. \$\endgroup\$ – Rene Saarsoo Sep 18 '13 at 13:42
7
\$\begingroup\$

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;
    }
  }
}
Improve this answer
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – 200_success Sep 18 '13 at 16:32
  • \$\begingroup\$ @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. \$\endgroup\$ – Guffa Sep 18 '13 at 17:29
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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