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

Programming Interviews: Exposed

Ace your Technical Interview Try Algorithms

In today's tight job market, competition for programming jobs is hotter than ever. This third edition of a popular guide to programming interviews includes new code examples, information on the latest languages, new chapters on sorting and design patterns, tips on using LinkedIn, and a downloadable app to help prepare applicants for the interview.

$ Check price
29.9929.99Amazon 4.5 logo(94+ reviews)

More Algorithms resources

Learn how data is stored

Data Structures and Algorithms in Java

Learn how data is stored Try Data Structures

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
64.9964.99Amazon 4.5 logo(97+ reviews)

More Data Structures resources

Ad