DSA Bubble Sort

Welcome to TheCodingCollege.com, your trusted resource for learning coding and programming concepts. In this article, we’ll delve into Bubble Sort, one of the simplest sorting algorithms, perfect for beginners stepping into the world of Data Structures and Algorithms (DSA).

What is Bubble Sort?

Bubble Sort is a straightforward comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

It’s called “Bubble Sort” because smaller elements “bubble up” to the top of the list (or larger elements sink to the bottom, depending on the sorting order).

Key Features of Bubble Sort

1. In-Place Sorting: Does not require additional storage; sorting is done within the array.
2. Stable Sorting: Does not change the relative order of equal elements.
3. Best for Learning: Easy to understand and implement.

How Does Bubble Sort Work?

Bubble Sort compares adjacent elements and swaps them if needed. The largest element “bubbles” to its correct position at the end of the array in each pass.

Steps:

1. Compare the first two elements.
2. Swap them if the first element is greater than the second.
3. Repeat this process for all pairs of adjacent elements in the array.
4. After the first pass, the largest element is at the correct position.
5. Repeat the process for the remaining unsorted part of the array.

Example of Bubble Sort

Let’s sort the array [5, 3, 8, 6, 2] in ascending order.

Initial Array: [5, 3, 8, 6, 2]

Pass 1:

• Compare 5 and 3 → Swap → [3, 5, 8, 6, 2]
• Compare 5 and 8 → No swap → [3, 5, 8, 6, 2]
• Compare 8 and 6 → Swap → [3, 5, 6, 8, 2]
• Compare 8 and 2 → Swap → [3, 5, 6, 2, 8]

Pass 2:

• Compare 3 and 5 → No swap → [3, 5, 6, 2, 8]
• Compare 5 and 6 → No swap → [3, 5, 6, 2, 8]
• Compare 6 and 2 → Swap → [3, 5, 2, 6, 8]
• Compare 6 and 8 → No swap → [3, 5, 2, 6, 8]

Pass 3:

• Compare 3 and 5 → No swap → [3, 5, 2, 6, 8]
• Compare 5 and 2 → Swap → [3, 2, 5, 6, 8]
• Compare 5 and 6 → No swap → [3, 2, 5, 6, 8]

Pass 4:

• Compare 3 and 2 → Swap → [2, 3, 5, 6, 8]

Sorted Array: [2, 3, 5, 6, 8]

Bubble Sort Code Implementation

Python Code:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Traverse the array
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap if elements are in the wrong order
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Example usage
array = [5, 3, 8, 6, 2]
bubble_sort(array)
print("Sorted Array:", array)

Output:

Sorted Array: [2, 3, 5, 6, 8]

Java Code:

class BubbleSort {
    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]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String args[]) {
        int arr[] = {5, 3, 8, 6, 2};
        bubbleSort(arr);
        System.out.print("Sorted Array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Time Complexity of Bubble Sort

Space Complexity: O(1)O(1) (In-place sorting).

Applications of Bubble Sort

1. Teaching Sorting: Ideal for introducing sorting concepts.
2. Small Datasets: Works well for small or nearly sorted data.
3. Debugging: Useful for debugging due to its simplicity.

Advantages and Disadvantages of Bubble Sort

Advantages

• Easy to understand and implement.
• Does not require additional memory.

Disadvantages

• Inefficient for large datasets.
• Comparatively slower than other sorting algorithms like Quick Sort or Merge Sort.

Conclusion

Bubble Sort is a great algorithm for beginners to grasp sorting concepts and develop a foundation in DSA. While it may not be the most efficient, its simplicity makes it a valuable tool for learning. Practice this algorithm and explore advanced sorting techniques at TheCodingCollege.com to enhance your programming skills.