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.

Visualization

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

Complexity

Time: O(n^{2}) 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(n^{2}) 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);
}

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.

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.