# Bubble Sort Algorithm in Java

This article gives provides an overview on Bubble Sort together with an implementation in Java.

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.

AttributeValue
ClassSorting Algorithm
ClassificationInternal, In-place, Stable Algorithm
Data StructureArray
Time Complexity: WorstO(n2)
Time Complexity: AverageO(n2)
Time Complexity: BestO(n)
Space Complexity: WorstO(1)

Algorithm Classification: Bubble Sort

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

## Pseudo-Code

This algorithm works by repeatedly iterating through the list of items and comparing adjacent elements. If an element is found to be larger than its neighbor, it is swapped with that element. This process is repeated until the list is sorted in ascending order.

procedure bubbleSort(list)
n = length of list
for i = 0 to n-1
for j = 0 to n-i-1
if list[j] > list[j+1]
swap(list[j], list[j+1])


The outer loop (the one with the variable i) is used to track the number of passes that have been made over the list. The inner loop (the one with the variable j) is used to compare the adjacent elements and perform the swap, if necessary.

The pseudo-code above uses a simple implementation of the bubble sort algorithm. There are several ways to optimize this algorithm, such as adding a flag to track whether any swaps were made during a pass, or using a more efficient sorting algorithm for lists that are already partially sorted.

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

}