Bubble Sort

Given an array of integers, your task is to sort the array in ascending order using the Bubble Sort algorithm.

Input Array:

Output Sorted Array:

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The largest unsorted element 'bubbles up' to its correct position after each pass.

Your goal is to return the sorted array after all necessary passes are completed.

Step-by-Step Solution: Understanding and Applying Bubble Sort

Problem Understanding: We are given an array of numbers and asked to sort them in increasing order. One simple way to do this is using Bubble Sort, a sorting algorithm that compares adjacent elements and repeatedly swaps them if they are in the wrong order.

The key idea is to "bubble up" the largest elements to the end of the array with each full pass through the list. This continues until the array is completely sorted.

Let’s Solve It with an Example:

Given the array: [5, 1, 4, 8, 2]

1. Start with the first two elements: 5 and 1. Since 5 > 1, we swap them. Now the array becomes: [1, 5, 4, 8, 2]
2. Compare 5 and 4. Swap again → [1, 4, 5, 8, 2]
3. Compare 5 and 8. No swap needed.
4. Compare 8 and 2. Swap → [1, 4, 5, 2, 8]

After the first pass, the largest number (8) is at the end. We repeat the process for the rest of the array (ignoring the sorted part at the end) until no more swaps are needed.

Handling Edge Cases

• Reverse Sorted Array (Worst Case): [3, 2, 1]
  Each element needs to travel all the way to its correct position. This requires the most comparisons and swaps.
• Already Sorted Array (Best Case): [1, 2, 3]
  If we add a small check to see whether any swaps were made in a pass, the algorithm can exit early. This saves time!
• Array with Duplicates: [4, 2, 2, 8, 4]
  Bubble Sort doesn’t mind repeated numbers. It compares them like any other values and puts them in the correct order: [2, 2, 4, 4, 8].
• Array with Negative Numbers: [5, -1, 0, -3]
  Works the same way. Negative numbers are handled just like positive ones. Final result: [-3, -1, 0, 5].
• Single Element: [7]
  No sorting is needed. The array is already sorted by default.
• Empty Array: []
  There's nothing to sort. The algorithm simply returns the empty array.

Final Thoughts:

Bubble Sort is great for understanding how sorting works because it’s simple and easy to follow. However, for large datasets, more efficient algorithms are preferred.

1. Start from the first element in the array.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, swap them.
4. Move to the next element and repeat steps 2 and 3 for the entire array.
5. After one complete pass, the largest element will be at the end.
6. Repeat the process for the remaining unsorted elements (excluding the last sorted ones).
7. Continue until the array is completely sorted.

Worked example

Let us take the followign array, and apply Bubble Sort algorithm to sort the array.

Pass 1

➜ Comparing 6 and 3

6 > 3.
Swap 6 and 3.
We need to arrange them in ascending order.

➜ Comparing 6 and 8

6 <= 8.
No swap needed.
They are already in ascending order.

➜ Comparing 8 and 2

8 > 2.
Swap 8 and 2.
We need to arrange them in ascending order.

➜ Comparing 8 and 7

8 > 7.
Swap 8 and 7.
We need to arrange them in ascending order.

➜ Comparing 8 and 4

8 > 4.
Swap 8 and 4.
We need to arrange them in ascending order.

8 is now at its correct position.

Pass 2

➜ Comparing 3 and 6

3 <= 6.
No swap needed.
They are already in ascending order.

➜ Comparing 6 and 2

6 > 2.
Swap 6 and 2.
We need to arrange them in ascending order.

➜ Comparing 6 and 7

6 <= 7.
No swap needed.
They are already in ascending order.

➜ Comparing 7 and 4

7 > 4.
Swap 7 and 4.
We need to arrange them in ascending order.

7 is now at its correct position.

Pass 3

➜ Comparing 3 and 2

3 > 2.
Swap 3 and 2.
We need to arrange them in ascending order.

➜ Comparing 3 and 6

3 <= 6.
No swap needed.
They are already in ascending order.

➜ Comparing 6 and 4

6 > 4.
Swap 6 and 4.
We need to arrange them in ascending order.

6 is now at its correct position.

Pass 4

➜ Comparing 2 and 3

2 <= 3.
No swap needed.
They are already in ascending order.

➜ Comparing 3 and 4

3 <= 4.
No swap needed.
They are already in ascending order.

4 is now at its correct position.

Pass 5

➜ Comparing 2 and 3

2 <= 3.
No swap needed.
They are already in ascending order.

3 is now at its correct position.

Pass 6

2 is now at its correct position.

Array is fully sorted.

#include <stdio.h>
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array is: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    bubble_sort(arr)
    print("Sorted array is:", arr)

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 7, 4};
        bubbleSort(arr);
        System.out.print("Sorted array is: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
}
const arr = [6, 3, 8, 2, 7, 4];
bubbleSort(arr);
console.log("Sorted array is:", arr);

package main
import "fmt"
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}
func main() {
    arr := []int{6, 3, 8, 2, 7, 4}
    bubbleSort(arr)
    fmt.Println("Sorted array is:", arr)
}

fn bubble_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}
fn main() {
    let mut arr = vec![6, 3, 8, 2, 7, 4];
    bubble_sort(&mut arr);
    println!("Sorted array is: {:?}", arr);
}

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}
fun main() {
    val arr = intArrayOf(6, 3, 8, 2, 7, 4)
    bubbleSort(arr)
    println("Sorted array is: ${arr.joinToString(" ")}")
}

func bubbleSort(_ arr: inout [Int]) {
    let n = arr.count
    for i in 0..<n-1 {
        for j in 0..<n-i-1 {
            if arr[j] > arr[j + 1] {
                arr.swapAt(j, j + 1)
            }
        }
    }
}
var arr = [6, 3, 8, 2, 7, 4]
bubbleSort(&arr)
print("Sorted array is:", arr)

function bubbleSort(arr: number[]): void {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
}
const arr: number[] = [6, 3, 8, 2, 7, 4];
bubbleSort(arr);
console.log("Sorted array is:", arr);

Time complexity

Space complexity

O(1)

Bubble Sort is an in-place sorting algorithm. It requires only a constant amount of extra space for swapping elements — typically a temporary variable and loop counters.