# 03. Bubble Sort

## Algorithm Pseudocode

1. Start at the outer loop, i = 0.
2. Within the inner loop, compare each two consecutive values.
3. If the value of the right cell has a key index lower than that of the left cell, swap.
4. Repeat inner/outer loops until smaller values bubble to the top.
5. *If no swaps occur in one entire inner loop, list is already sorted and you're done.

## Visualization

Here's a good visualization as to what's exactly happening.

## Complexity

Time: O(n2) but O(n) when nearly sorted.

Space: O(1)

## Characteristics

Bubble sort is a stable sorting algorithm.

Bubble sort has a high overhead. In the case where the given input is reversed, the algorithm will take O(n2) time.

## Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

``````import java.util.Arrays;

public class BubbleSort extends Sort {

public static void main(String[] args) {

int[] testInt = {1,6,2,3,6,7,4,2,5};
bubbleSort(testInt);
System.out.println(Arrays.toString(testInt));
}

public static void bubbleSort(int[] testInt) {

/**
* If flag keeps false, then no swaps occurred, meaning
* our list is already sorted
*/
boolean flag;

do {

flag = false;

for (int j = 0; j < testInt.length-1; j++) {

if (testInt[j+1] < testInt[j]) {
swap(testInt, j, j+1);
flag = true;
}

}

} while (flag);
}

``````

### Aching back from coding all day?

#### Self-Massage Tool

Relieve spasms, tight muscles, trigger points and pressure points with the Body Back Buddy! This trigger point massage is designed to help you self-message any area of your body - especially those that are hard to reach. Keeping your muscles relaxes and out of contraction is importan in helping to reduce pain and prevent muscle injury.

\$ Check price
(3,443+ reviews)