AlgoDaily

Fundamental Sorting Algorithms: Bubble and Insertion

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Introduction

This tutorial is about two fundamental, and basic, sorting algorithms. If you are new to sorting, I'd recommend you come up with your own algorithm for sorting arrays first, and then compare it with these algorithms. These fundamental sorting techniques give you important insights into:

  1. How to sort arrays
  2. How you can improve an algorithm, and
  3. Under what conditions you should apply a certain sort procedure
```java
import java.util.*;

class bubbleSort
{
    static void swap(int[]X,int ind1,int ind2)
    {
        int temp = X[ind1];
        X[ind1] = X[ind2];
        X[ind2] = temp;
    }
    public static void sort(int []X)
    {
        int n = X.length;
        boolean sorted = false;
        int totalSorted = 0;
        while (totalSorted < (n-1) && !sorted)
        {
            sorted = true;     //will remain true if no swaps are made
            for(int i = 1; i <= n-1-totalSorted; ++i)
            {
                if (X[i-1] > X[i])
                {
                    swap(X, i-1, i);
                    sorted = false;
                }
            }
            totalSorted++;
        }
    }
}

class insertionSort
{
    static void swap(int[]X,int ind1,int ind2)
    {
        int temp = X[ind1];
        X[ind1] = X[ind2];
        X[ind2] = temp;
    }
    
    public static void sort(int []X)
    {
        int totalSorted = 1;
        int n = X.length;
        while (totalSorted <= (n-1))
        {
            //insert the item at index position totalSorted into top half
            //by successive comparison with items before it
            int i = totalSorted;
            while(i > 0 && X[i-1] > X[i])
            {
                swap(X, i-1, i);
                i--;
            }
            totalSorted++;
        }
    }
}
public class Main
{
    static void printArray(int []X)
    {
        for (int i = 0; i < X.length; ++i)
            System.out.print(X[i] + " ");
        System.out.println(" ");
    }
    
    public static void main(String args[]) {
        int myArr1[] = {1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2};
        bubbleSort.sort(myArr1);
        printArray(myArr1);
        
        int myArr2[] = {1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2};
        insertionSort.sort(myArr2);
        printArray(myArr2);
    }
}
```
```javascript
function swap(X, ind1, ind2) {
    let temp = X[ind1];
    X[ind1] = X[ind2];
    X[ind2] = temp;
}

function bubbleSort(X) {
    let n = X.length;
    let sorted = false;
    let totalSorted = 0;
    while (totalSorted < (n-1) && !sorted) {
        sorted = true;
        for(let i = 1; i <= n-1-totalSorted; ++i) {
            if (X[i-1] > X[i]) {
                swap(X, i-1, i);
                sorted = false;
            }
        }
        totalSorted++;
    }
}

function insertionSort(X) {
    let totalSorted = 1;
    let n = X.length;
    while (totalSorted <= (n-1)) {
        let i = totalSorted;
        while(i > 0 && X[i-1] > X[i]) {
            swap(X, i-1, i);
            i--;
        }
        totalSorted++;
    }
}

function printArray(X) {
    console.log(X.join(' ') + ' ');
}

let myArr1 = [1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2];
bubbleSort(myArr1);
printArray(myArr1);

let myArr2 = [1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2];
insertionSort(myArr2);
printArray(myArr2);
```
```python
def swap(X, ind1, ind2):
    temp = X[ind1]
    X[ind1] = X[ind2]
    X[ind2] = temp

def bubble_sort(X):
    n = len(X)
    sorted = False
    total_sorted = 0
    while total_sorted < (n-1) and not sorted:
        sorted = True
        for i in range(1, n-1-total_sorted+1):
            if X[i-1] > X[i]:
                swap(X, i-1, i)
                sorted = False
        total_sorted += 1

def insertion_sort(X):
    total_sorted = 1
    n = len(X)
    while total_sorted <= (n-1):
        i = total_sorted
        while i > 0 and X[i-1] > X[i]:
            swap(X, i-1, i)
            i -= 1
        total_sorted += 1

def print_array(X):
    print(" ".join(map(str, X)), " ")

myArr1 = [1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2]
bubble_sort(myArr1)
print_array(myArr1)

myArr2 = [1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2]
insertion_sort(myArr2)
print_array(myArr2)
```
```cpp
#include <iostream>
#include <vector>

void swap(std::vector<int>& X, int ind1, int ind2) {
    int temp = X[ind1];
    X[ind1] = X[ind2];
    X[ind2] = temp;
}

void bubbleSort(std::vector<int>& X) {
    int n = X.size();
    bool sorted = false;
    int totalSorted = 0;
    while (totalSorted < (n-1) && !sorted) {
        sorted = true;
        for(int i = 1; i <= n-1-totalSorted; ++i) {
            if (X[i-1] > X[i]) {
                swap(X, i-1, i);
                sorted = false;
            }
        }
        totalSorted++;
    }
}

void insertionSort(std::vector<int>& X) {
    int totalSorted = 1;
    int n = X.size();
    while (totalSorted <= (

n-1)) {
        int i = totalSorted;
        while(i > 0 && X[i-1] > X[i]) {
            swap(X, i-1, i);
            i--;
        }
        totalSorted++;
    }
}

void printArray(const std::vector<int>& X) {
    for (int i = 0; i < X.size(); ++i) {
        std::cout << X[i] << " ";
    }
    std::cout << " " << std::endl;
}

int main() {
    std::vector<int> myArr1 = {1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2};
    bubbleSort(myArr1);
    printArray(myArr1);

    std::vector<int> myArr2 = {1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2};
    insertionSort(myArr2);
    printArray(myArr2);

    return 0;
}
```
```csharp
using System;

class Sorting
{
    static void Swap(int[] X, int ind1, int ind2)
    {
        int temp = X[ind1];
        X[ind1] = X[ind2];
        X[ind2] = temp;
    }

    public static void BubbleSort(int[] X)
    {
        int n = X.Length;
        bool sorted = false;
        int totalSorted = 0;
        while (totalSorted < (n-1) && !sorted)
        {
            sorted = true;
            for(int i = 1; i <= n-1-totalSorted; ++i)
            {
                if (X[i-1] > X[i])
                {
                    Swap(X, i-1, i);
                    sorted = false;
                }
            }
            totalSorted++;
        }
    }

    public static void InsertionSort(int[] X)
    {
        int totalSorted = 1;
        int n = X.Length;
        while (totalSorted <= (n-1))
        {
            int i = totalSorted;
            while(i > 0 && X[i-1] > X[i])
            {
                Swap(X, i-1, i);
                i--;
            }
            totalSorted++;
        }
    }

    public static void PrintArray(int[] X)
    {
        Console.WriteLine(String.Join(" ", X) + " ");
    }

    public static void Main(string[] args)
    {
        int[] myArr1 = {1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2};
        BubbleSort(myArr1);
        PrintArray(myArr1);

        int[] myArr2 = {1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2};
        InsertionSort(myArr2);
        PrintArray(myArr2);
    }
}
```
```go
package main

import "fmt"

func swap(X []int, ind1, ind2 int) {
	temp := X[ind1]
	X[ind1] = X[ind2]
	X[ind2] = temp
}

func bubbleSort(X []int) {
	n := len(X)
	sorted := false
	totalSorted := 0
	for totalSorted < (n-1) && !sorted {
		sorted = true
		for i := 1; i <= n-1-totalSorted; i++ {
			if X[i-1] > X[i] {
				swap(X, i-1, i)
				sorted = false
			}
		}
		totalSorted++
	}
}

func insertionSort(X []int) {
	totalSorted := 1
	n := len(X)
	for totalSorted <= (n - 1) {
		i := totalSorted
		for i > 0 && X[i-1] > X[i] {
			swap(X, i-1, i)
			i--
		}
		totalSorted++
	}
}

func printArray(X []int) {
	for i := 0; i < len(X); i++ {
		fmt.Print(X[i], " ")
	}
	fmt.Println(" ")
}

func main() {
	myArr1 := []int{1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2}
	bubbleSort(myArr1)
	printArray(myArr1)

	myArr2 := []int{1, 9, 321, 234, 12, 21, 5, 3, 1, 12, 11, 22, 33, 1, 4, 5, 3, 21, 2}
	insertionSort(myArr2)
	printArray(myArr2)
}
```

Bubble Sort

Bubble Sort

Bubble sort is one of the simplest sorting methods. In case you are wondering where this odd name for a sorting technique came from-- lighter bubbles in water always float to the top. Heavy objects sink to the bottom.

We use a similar idea when sorting items in an array: "bubble down" heavier or bigger keys. Alternatively, we can bubble up lighter keys.

Let's take a look at this technique that bubbles down all the heavier keys to the end of the array. Bubble sort divides the entire array into a sorted half and an unsorted half. It works by using the following principle:

  1. Maintain an unsorted left sub-array and a sorted right sub-array.
  2. Bubble down the heaviest item in the unsorted half to the right sub-array.

How do you bubble down the heaviest key? One way of doing it is by comparing consecutive keys and swapping if left key is greater than the right key. Here is the complete pseudo-code:

Routine: bubbleSort
Input: Unsorted array X of size n

1. sorted = false
2. totalSorted = 0
3. while (totalSorted < (n-1) and !sorted)
    {
        a.sorted = true     // will remain true if no swaps are made
        b. for i=1 .. (n-1 - totalSorted)
        {
            i. if X[i-1] > X[i]
                {     swap(X[i-1],X[i])
                      sorted = false
                }
        }
        c. totalSorted++
    }

```java
public class Main {
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap here
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1};
        bubbleSort(arr);
    }
}
```
```javascript
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap here
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  console.log(arr);
}

bubbleSort([3, 2, 1]);
```
```python
def bubbleSort(arr):
    for i in range(0, len(arr)):
        for j in range(0, len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap here
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp

    print(arr)

bubbleSort([3, 2, 1])
```
```cpp
#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr.size() - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap here
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr = {3, 2, 1};
    bubbleSort(arr);
    return 0;
}
```
```csharp
using System;

class MainClass {
    public static void BubbleSort(int[] arr) {
        for (int i = 0; i < arr.Length; i++) {
            for (int j = 0; j < arr.Length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap here
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        Console.WriteLine(String.Join(" ", arr));
    }

    public static void Main(string[] args) {
        int[] arr = {3, 2, 1};
        BubbleSort(arr);
    }
}
```
```go
package main

import "fmt"

func bubbleSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j] > arr[j+1] {
				// Swap here
				temp := arr[j]
				arr[j] = arr[j+1]
				arr[j+1] = temp
			}
		}
	}

	for i := 0; i < len(arr); i++ {
		fmt.Print(arr[i], " ")
	}
	fmt.Println()
}

func main() {
	arr := []int{3, 2, 1}
	bubbleSort(arr)
}
```

Question 1

Which is correct when looking at bubble sort's time complexity?

Bubble Sort Continued

Notice how beautifully the pseudo-code sorts the array. The outer loop of the algorithm represents a pass of the algorithm. The inner for loop compares consecutive items and swaps them if needed.

The boolean flag sorted is set to true before the inner for-loop for comparing successive items. If no swap is made, it remains true and we can break out of the outer loop.

This makes bubble sort a very special algorithm, as it is one of the few sorting algorithms that tells you when an array is sorted. You can stop running further passes if the array is sorted. The entire process is illustrated in the figure below. Notice how the sorted and unsorted parts of the array is maintained, and how the algorithm stops once the array is sorted.

bubble sort

Complexity of Bubble Sort

The time complexity of bubble sort depends upon the input array. As we saw in our pseudo-code, if our array is already sorted, it will make only one pass through the input array. Hence, for a sorted array, its time complexity is O(n). However, in the worst-case scenario, it will make roughly O(n) passes through the array, where each pass is approximately O(n) time. This makes the overall time complexity quadratic, i.e., O(n$^2$) in the worst case.

The sorting is in place sorting and does not use any extra array memory. Thus the space complexity is O(1).

Insertion Sort

Insertion Sort

Insertion sort is another marvelous sorting algorithm, one that's pretty simple to understand and easy to implement.

The idea is similar to bubble sort. Think of your input array as being made of a sorted left half and an unsorted right half.

One by one, insert an item in its correct place in the sorted half. Insertion is done by comparing the item with successive items before it, and swapping them if needed. To reiterate the steps:

  1. Maintain a sorted left sub-array and an unsorted right sub-array.
  2. Insert the first key from the unsorted part into its correct place in the sorted half.

The entire pseudo-code that accomplishes the sort is provided here:

Routine: insertionSort
Input: Unsorted array X of size n

1. totalSorted = 1
2. while totalSorted <= (n-1)
    {
        // insert the item at index position totalSorted into top half
        // by successive comparison with items before it
        b. i = totalSorted
        c. while(i > 0 and X[i-1]>X[i])
        {
            i. swap(X[i-1], X[i])
            ii. i--
        }
        totalSorted++
    }

```java
public class Main {
    public static int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];

            // Arrange the elements prior to the current
            // but greater than it to one position ahead
            int j = i - 1;
            while (j >= 0 && val < arr[j]) {
                arr[j + 1] = arr[j];
                j -= 1;
            }
            arr[j + 1] = val;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {41, 19, 23, 3, 4, 19};
        int[] sortedArr = insertionSort(arr);
        for (int i : sortedArr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
```
```javascript
function insertionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    const val = arr[i];

    // Arrange the elements prior to the current
    // but greater than it to one position ahead
    let j = i - 1;
    while (j >= 0 && val < arr[j]) {
      arr[j + 1] = arr[j];
      j -= 1;
    }
    arr[j + 1] = val;
  }
  return arr;
}

const arr = [41, 19, 23, 3, 4, 19];
console.log(insertionSort(arr));
```
```python
def insertion_sort(arr):
    for i in range(1, len(arr)):  
        val = arr[i]

        # Arrange the elements prior to the current
        # but greater than it to one position ahead
        j = i-1
        while j >= 0 and val < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = val
    return arr
  

arr = [41, 19, 23, 3, 4, 19]
print(insertion_sort(arr))
```
```cpp
#include <iostream>
#include <vector>

std::vector<int> insertionSort(std::vector<int> arr) {
    for (int i = 1; i < arr.size(); i++) {
        int val = arr[i];

        // Arrange the elements prior to the current
        // but greater than it to one position ahead
        int j = i - 1;
        while (j >= 0 && val < arr[j]) {
            arr[j + 1] = arr[j];
            j -= 1;
        }
        arr[j + 1] = val;
    }
    return arr;
}

int main() {
    std::vector<int> arr = {41, 19, 23, 3, 4, 19};
    std::vector<int> sortedArr = insertionSort(arr);
    for (int i : sortedArr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;
}
```
```csharp
using System;

class MainClass {
    public static int[] InsertionSort(int[] arr) {
        for (int i = 1; i < arr.Length; i++) {
            int val = arr[i];

            // Arrange the elements prior to the current
            // but greater than it to one position ahead
            int j = i - 1;
            while (j >= 0 && val < arr[j]) {
                arr[j + 1] = arr[j];
                j -= 1;
            }
            arr[j + 1] = val;
        }
        return arr;
    }

    public static void Main(string[] args) {
        int[] arr = {41, 19, 23, 3, 4, 19};
        int[] sortedArr = InsertionSort(arr);
        Console.WriteLine(String.Join(" ", sortedArr));
    }
}
```
```go
package main

import "fmt"

func insertionSort(arr []int) []int {
	for i := 1; i < len(arr); i++ {
		val := arr[i]

		// Arrange the elements prior to the current
		// but greater than it to one position ahead
		j := i - 1
		for j >= 0 && val < arr[j] {
			arr[j+1] = arr[j]
			j -= 1
		}
		arr[j+1] = val
	}
	return arr
}

func main() {
	arr := []int{41, 19, 23, 3, 4, 19}
	sortedArr := insertionSort(arr)
	for i := 0; i < len(sortedArr); i++ {
		fmt.Print(sortedArr[i], " ")
	}
	fmt.Println()
}
```

Question 2

Which is correct when looking at insertion sort's time complexity?

Insertion Sort Continued

Again, what a marvelous piece of code! It's sorting an entire array in a simple manner. The outer loop represents a pass of the algorithm and the inner loop inserts one item from the unsorted part into the sorted part by successive comparisons. The whole process is illustrated in the figure below. Notice how the big bubbles illustrate the insertion process of the inner loop.

insertion sort

Complexity of Insertion Sort

Insertion sort, like bubble sort, has a time complexity that depends upon the input array.

We can see that if we input a sorted array, then insertion sort makes only one pass through the array, and thus its time complexity is O(n). However, in the worst-case scenario (say the input array is in descending order) then there are O(n) items to be inserted. Each insertion would make roughly O(n) comparisons, giving an overall quadratic time complexity-- O(n$^2$).

The sorting is in place and does not require any extra array memory making its space complexity O(1).

0

Wrapping up

Wrapping up

In summary, insertion sort and bubble sort are great sorting algorithms. You can use them if you have a very small array and want a quick implementation. Here's a really important point:

If you know in advance that your array is almost sorted, then both bubble sort and insertion sort would be very efficient.

However, if you know nothing about your array (or you have a large array), then go for a more efficient algorithm.

I hope you enjoyed this tutorial on basic sorting algorithms. Good luck sorting!

0

Question 3

Which is correct when looking at bubble sort's space complexity?

Question 4

Which is correct when looking at insertion sort's space complexity?

One Pager Cheat Sheet

One Pager Cheat Sheet

  • If you are new to sorting, come up with your own algorithm first and then compare it to the fundamental sorting techniques to gain important insights into how to sort arrays, improve an algorithm and when to apply a certain sort procedure.
  • Bubble sort starts by dividing the array into a sorted and unsorted sub-array, and compares consecutive items to sort them by "bubbling down" heavier items and "bubbling up" lighter items.
  • Bubble Sort has a time complexity of O(n^2), as it must compare all consecutive pairs and perform a swap operation for each comparison, with a total of n * (n-1) / 2 comparisons necessary.
  • Bubble sort is a very special algorithm which is one of the few sorting algorithms that tells you when an array is sorted and can stop running further passes if the array is already sorted, thus having an O(n) best-case complexity and an O(n$^2$) worst-case complexity with an O(1) space complexity.
  • Insertion Sort is an easy-to-implement algorithm that swaps items if needed in order to insert them in their correct place in the sorted sub-array.
  • Insertion Sort has a worst-case time complexity of O(n$^2$), due to needing to iterate through the sorted sub-array and compare each element to each item before it in an O(n) operation.
  • Insertion sort is an in place sorting algorithm which has time complexity of O(n) if the input is already sorted, and worst case time complexity of O(n$^2$) if the input is in descending order.
  • If you know in advance that your array is almost sorted, then **both bubble sort and insertion sort would be very efficient**.
  • Bubble sort is an in-place sorting algorithm with O(1) space complexity, making it an efficient method for sorting data.
  • Insertion Sort has excellent `space complexity of O(1), requiring only **constant extra space.
Open interactive view →