Bubble sort is sometimes referred to as sinking sort. The bubble sort algorithm repeatedly steps through the list and compare each adjacent item. The pair of values gets swapped if they are in the wrong order. The algorithm gets its name from the way smaller or larger elements “bubble” to the top of the list.

#### Algorithm Classification

The following table contains information about the analysis of the BubbleSort algorithm. It defines the worst, average and best cases in terms of time complexity and also the worst case in space complexity.

Attribute | Value |
---|---|

Class | Sorting Algorithm |

Classification | Internal, In-place, Stable Algorithm |

Data Structure | Array |

Time Complexity: Worst | O(n^{2}) |

Time Complexity: Average | O(n^{2}) |

Time Complexity: Best | O(n) |

Space Complexity: Worst | O(1) |

Please use the following link for an explanation on Big-O notation and what is good, fair and bad.

#### BubbleSort In Java

The BubbleSort class implements the BubbleSort algorithm for sorting an array of integers.

```
public final class BubbleSort {
public void sort(int[] collection) {
if (collection != null) {
bubbleSort(collection);
} else {
throw new IllegalArgumentException("Input parameter for array to sort is null.");
}
}
private void bubbleSort(int[] collection) {
int n = collection.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (collection[j] > collection[j+1]) {
swap(collection, j, j+1);
}
}
}
}
private void swap(int[] collection, int x, int y) {
int temp = collection[x];
collection[x] = collection[y];
collection[y] = temp;
}
}
```

#### Conclusions

The BubbleSort algorithm forms part of a larger group of sorting algorithms. Learning through experience is the reason I created this post about the implementation of the BubbleSort algorithm in Java. I have learned a lot about how others have solved the BubbleSort algorithm in other languages including different implementations in Java.

Learning how to solve difference problems and algorithms with certain techniques, one starts to develop certain pattern recognition abilities which will help you in future when similar problems arise.

#### Sample Code (GitHub)

The code example can be downloaded from Github from the button below.