Algorithm

The Bubble Sort algorithm works by repeatedly stepping through the list of elements to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Here's a step-by-step explanation of the algorithm:

  1. Start from the first element (index 0) and compare it with the next element (index 1).

    • If the first element is greater than the second element, swap them.
    • If the first element is smaller or equal to the second element, do nothing.

  2. Move to the next pair of elements (index 1 and index 2) and repeat the comparison and swapping process.

    • Continue this process until you reach the end of the list.

  3. After the first pass, the largest element will have "bubbled up" to the end of the list.

    • The last element is now in its correct sorted position.

  4. Repeat the process for the remaining elements (excluding the last one).

    • On each pass, the next largest element will be placed in its correct position.

  5. Continue these passes until no more swaps are needed.

    • If, after a pass, no swaps were made, it means the list is fully sorted, and the algorithm can stop.

Here's a simple example of the Bubble Sort algorithm in action:

Initial list: [5, 3, 8, 4, 2]

  1. Pass 1:

    • Compare 5 and 3, swap them → [3, 5, 8, 4, 2]
    • Compare 5 and 8, do nothing
    • Compare 8 and 4, swap them → [3, 5, 4, 8, 2]
    • Compare 8 and 2, swap them → [3, 5, 4, 2, 8]

  2. Pass 2:

    • Compare 3 and 5, do nothing
    • Compare 5 and 4, swap them → [3, 4, 5, 2, 8]
    • Compare 5 and 2, swap them → [3, 4, 2, 5, 8]

  3. Pass 3:

    • Compare 3 and 4, do nothing
    • Compare 4 and 2, swap them → [3, 2, 4, 5, 8]

  4. Pass 4:

    • Compare 3 and 2, swap them → [2, 3, 4, 5, 8]

After Pass 4, no more swaps are needed, and the list [2, 3, 4, 5, 8] is sorted.

Keep in mind that Bubble Sort is not the most efficient sorting algorithm for large datasets, and it has a time complexity of O(n^2). Other more efficient algorithms like QuickSort or MergeSort are often preferred in practice.

 

Code Examples

#1 Bubble Sort implement in Python

Code - Python Programming

def bubble_sort(arr):
    n = len(arr)

    # Traverse through all elements in the list
    for i in range(n):
        # Last i elements are already sorted, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)

print("Sorted array:", my_list)
Copy The Code & Try With Live Editor

#2 Bubble Sort implement in Java

Code - Java Programming

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};

        System.out.println("Original array:");
        printArray(array);

        bubbleSort(array);

        System.out.println("\nSorted array:");
        printArray(array);
    }

    // Function to perform Bubble Sort on an array
    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++) {
                // Swap if the element found is greater than the next element
                if (arr[j] > arr[j + 1]) {
                    // swap temp and arr[i]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // Function to print an array
    static void printArray(int[] arr) {
        for (int i = 0; i  <  arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
Copy The Code & Try With Live Editor

#3 Bubble Sort implement in C

Code - C Programming

#include <stdio.h>

// Function to perform bubble sort on an array
void bubbleSort(int arr[], int n) {
    for (int i = 0; i  <  n - 1; i++) {
        for (int j = 0; j  <  n - i - 1; j++) {
            // Swap if the element found is greater
            // than the next element
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j + 1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i  <  size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Bubble Sort implement in C++

Code - C++ Programming

#include <iostream>

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void bubbleSort(int arr[], int n) {
    for (int i = 0; i  <  n - 1; i++) {
        for (int j = 0; j  <  n - i - 1; j++) {
            // If the element found is greater than the next element, swap them
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    printArray(arr, n);

    bubbleSort(arr, n);

    std::cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Bubble Sort Data Structure and Algorithm