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(n²) 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²) 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);
  }

04. Insertion Sort
02. Selection Sort

Ace your Technical Interview

Elements of Programming Interviews

Learn all the different scenarios of . This book is jam packed with code snippets written in C++ and Java to give you the edge you need to ace your technical interviews. Problems come with detailed solutions as well as a hint in case you get stuck, and organized by difficulty level with several variants to help you apply your knowledge more widely.

$ Check price
Amazon 4 logo

(240+ reviews)

More Algorithms resources

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
Amazon 4.5 logo

(3,443+ reviews)