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

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

Time: `O(n ^{2})` but

Space: `O(1)`

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(n ^{2})` time.

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);
}
```

Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming.

$ Check price(418+ reviews)

Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate.

$ Check price(97+ reviews)

Ad