03. Bubble Sort
Algorithm Pseudocode
- 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.
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);
}
Ace your Technical Interview
Introduction to Algorithms
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) 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) Ad