1. Tutorials
2. Algorithms
3. Sorting
4. Bubble Sort

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.

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

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
9999(418+ reviews)

More Algorithms resources

Learn how data is stored

Data Structures and Algorithms in Java

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.99(97+ reviews)

More Data Structures resources

Ad