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 Optimized Bubble Sort in Python

Code - Python Programming

def optimized_bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        # Set a flag to optimize by checking if any swapping occurs in the inner loop
        swapped = False
        
        # Last i elements are already sorted, so no 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]
                swapped = True
        
        # If no swapping occurred in the inner loop, the array is already sorted
        if not swapped:
            break

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

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

#2 Optimized Bubble Sort 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);

        // Apply the optimized bubble sort
        bubbleSort(array);

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

    static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        for (int i = 0; i  <  n - 1; i++) {
            swapped = false;

            for (int j = 0; j  <  n - i - 1; j++) {
                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;

                    swapped = true;
                }
            }

            // If no two elements were swapped in the inner loop, the array is already sorted
            if (!swapped) {
                break;
            }
        }
    }

    static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
Copy The Code & Try With Live Editor

#3 Optimized Bubble Sort in C

Code - C Programming

#include <stdio.h>

void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void optimizedBubbleSort(int arr[], int n) {
    int i, j;
    int swapped;

    for (i = 0; i  <  n-1; i++) {
        swapped = 0; // Flag to check if any swapping occurred in this pass

        for (j = 0; j  <  n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                swapped = 1; // Set the flag to indicate swapping occurred
            }
        }

        // If no two elements were swapped by inner loop, the array is sorted
        if (swapped == 0) {
            break;
        }
    }
}

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

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

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

    optimizedBubbleSort(arr, n);

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

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

#4 Optimized Bubble Sort in C++

Code - C++ Programming

start coding...
Copy The Code & Try With Live Editor
Advertisements

Demonstration