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

Ace your Technical Interview

Elements of Programming Interviews

Ace your Technical Interview Try Algorithms

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
39.9539.95Amazon 4 logo(240+ reviews)

More Algorithms resources

Aching back from coding all day?

Self-Massage Tool

Aching back from coding all day? Try Back Problems

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
29.9529.95Amazon 4.5 logo(3,443+ reviews)

More Back Problems resources

Ad