# Bubble sorting an int array

I'd like to improve this bubble sort code

 package com.arun.sort;

import java.util.Arrays;

public class BubbleSort {

public static void main(String[] args) {

int[] arr={2,5,1,8,12,3,7};
int n=arr.length;

for(int k=0;k<n-1;k++){
for(int i=0;i<n-k-1;i++){
if(arr[i]>arr[i+1]){
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
}

System.out.println("Sorted array" +Arrays.toString(arr));

}

}

-
I'm assuming you know this, and that the bubble sort is an exercise, but the easiest way to improve on this would be to choose anything but a bubble sort. As far as I know, there are no use-cases where the bubble sort isn't the worst performing sort algorithm. – Dominic Cronin Jul 27 '14 at 13:05
@DominicCronin - for empty-set data, bubblesort is among the fastest ... ;-) – rolfl Jul 27 '14 at 13:15
@rolfl :-) For an empty dataset, the "Don't sort" algorithm is even faster. – Dominic Cronin Jul 27 '14 at 16:21
@DominicCronin: rotating drum (i.e. not random-access) storage, with suitable constraints (not sure exactly: I suppose a read head at least one record before the write head or something along those lines?), bubble sort is not only useful it's optimal. Whether that can still be called a "use-case" in 2014 is another matter. – Steve Jessop Jul 27 '14 at 18:01
Steve Jessop - interesting - got a reference? – Dominic Cronin Jul 27 '14 at 21:52

### Step 1: format it nicely

An IDE can automatically reformat code nicely to follow the standard:

int n = arr.length;

for (int k = 0; k < n - 1; k++) {
for (int i = 0; i < n - k - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}


In Eclipse it's Control-Shift-f. It adds spaces around operators. Now the code looks like the standard, and it's easier to read and code review for everyone.

### Step 2: extract to a method

In the current code you have a hardcoded array, and the main logic follows right after. It's hard to test this way. What if you want to see if the implementation works with a different set of numbers? You have to rewrite the array. Better to extract the main logic into its own, independent method:

void sort(int[] arr) {
// ...
}


Now you can test with multiple different inputs easier:

arr = new int[]{2, 5, 1, 8, 12, 3, 7};
BubbleSort.sort(arr);
System.out.println(Arrays.toString(arr));

arr = new int[]{4, 3, 2, 1, 2};
BubbleSort.sort(arr);
System.out.println(Arrays.toString(arr));


### Step 3: convert print statements to proper unit tests

The problem with print statements is that every time you change something and rerun, you have to re-verify the output of each statement. Unit tests can automate the verification step, and converting is easy enough to do:

@Test
public void testMixedValues() {
int[] arr = {2, 5, 1, 8, 12, 3, 7};
BubbleSort.sort(arr);
assertEquals("[1, 2, 3, 5, 7, 8, 12]", Arrays.toString(arr));
}

@Test
public void testDecreasingValues() {
int[] arr = {4, 3, 2, 1};
BubbleSort.sort(arr);
assertEquals("[1, 2, 3, 4]", Arrays.toString(arr));
}

@Test
public void testDecreasingWithDups() {
int[] arr = {4, 3, 2, 1, 2, 3, 2};
BubbleSort.sort(arr);
assertEquals("[1, 2, 2, 2, 3, 3, 4]", Arrays.toString(arr));
}


Btw, I didn't type the expected strings in the assertEquals. I wrote the test cases first, with "" as the expected values, and ran the tests. All the tests failed, of course, but the error messages told me the actual values that were different from the expected "". I verified that they are correct and copy-pasted the correct texts into the test cases.

Now you can make changes and the test cases will flag an error if something breaks. Unless you do something really horrible, typically only a few of the test cases will break, and you don't need to reverify the others that are still working, which makes debugging a lot easier.

### Minor things

Instead of n, a better name would be length to cache the length of the array.

As for the loop variables, it's more traditional to name nested counter variables as i, j, k, in this order of nesting level, instead of k, i as you did. In any case, this is really not a big deal.

int length = arr.length;

for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}

-

API (or the lack of one):

As it stands, we can't sort any array except the one you've hard coded into the main method. You should create a separate bubbleSort method that accepts an array of numbers as a parameter. Then we could call that method from main, or anywhere really.

Naming:

It's hard. Really hard, but I recommend against one and two letter variable names. It tends to obfuscate the code and make it hard to follow. I don't like having to map meanings in my head. That's even harder than naming things.

• n could be something like initialLength or arrLength.
• i, j, & k are traditionally used for loop indexes, but I don't like them in nested loops. I prefer inner and outer when lacking a better index name. If you stick with them though, the outer most loop should be i moving up the alphabet to j for the inner loop.
• temp? Temp what?! Try tempValue.

Note that the naming stuff is nitpicky, but the code structure is not. You shouldn't program right inside main like that.

-
I'm not sure I agree with tempValue: it adds length to the identifier without really adding any meaning. – Hurkyl Jul 27 '14 at 12:45
@Hurkyl I agree that it's not a great alternative, but I think it does clarify that the code sorts the array in place and that temp is a value and not a temporary array. – RubberDuck Jul 27 '14 at 12:50
i, j and k are so embedded in programming culture as loop indices (ever since that's where integers began in Fortran), that it's probably OK to use them for that. I do. Still - I prefer to use i for the outermost loop, and so on. – Dominic Cronin Jul 27 '14 at 13:01
That's a good point @DominicCronin and I mentioned that, but just because something "has always been that way" doesn't make it right or good. I will update my answer with the part about i being the outer most loop though. – RubberDuck Jul 27 '14 at 13:06

Let me start with the glaring issue, I want to get that done, and leave the rest to others,,

# Formatting

Your code formatting is messy. there is just three things that are not indented in a java-file as per conventions.

these three things are:

1. Package-declaration
2. Import statements
3. Class-opening and closing

Everything else is usually indented by either 4 spaces or 1 tab, in the least!
You nicely indented your for-loops though ;)

In addition to that, your operators and statements are a bit very cramped.
Oracle advises to and uses a few tricks to make operations more visible to the programmer:

• Arithmetic operators (+,-,*,/,<,>) have a space before and after
• Same goes for logical operators (&&,||,...)
• before opening and after closing parentheses there is a space, but not if it's respectively after or before another parenthesis.
-
I am not going to add a comment on the overuse of newlines here, because I feel that the other problems are more in need of help. – Vogel612 Jul 27 '14 at 11:30
Thanks. I ll keep these suggestions in mind. – Arun Prakash Jul 27 '14 at 11:49