Bubble Sort Program

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps 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. It's not an efficient algorithm for large lists, but it's easy to understand and implement.

Problem Statement

Given an array of integers, we need to sort it using the Bubble Sort algorithm in ascending order.

Example

Let's take an example array: [9, 2, 1, 6, -3, 7, -2, 1, -5, 12]

Pass 1:

• Compare 9 and 2: Swap them → [2, 9, 1, 6, -3, 7, -2, 1, -5, 12]
• Compare 9 and 1: Swap them → [2, 1, 9, 6, -3, 7, -2, 1, -5, 12]
• Compare 9 and 6: Swap them → [2, 1, 6, 9, -3, 7, -2, 1, -5, 12]
• Compare 9 and -3: Swap them → [2, 1, 6, -3, 9, 7, -2, 1, -5, 12]
• Compare 9 and 7: Swap them → [2, 1, 6, -3, 7, 9, -2, 1, -5, 12]
• Compare 9 and -2: Swap them → [2, 1, 6, -3, 7, -2, 9, 1, -5, 12]
• Compare 9 and 1: Swap them → [2, 1, 6, -3, 7, -2, 1, 9, -5, 12]
• Compare 9 and -5: Swap them → [2, 1, 6, -3, 7, -2, 1, -5, 9, 12]
• Compare 9 and 12: No swap → [2, 1, 6, -3, 7, -2, 1, -5, 9, 12]

Pass 2:

• Compare 2 and 1: Swap them → [1, 2, 6, -3, 7, -2, 1, -5, 9, 12]
• Compare 6 and -3: Swap them → [1, 2, -3, 6, 7, -2, 1, -5, 9, 12]
• Compare 6 and 7: No swap → [1, 2, -3, 6, 7, -2, 1, -5, 9, 12]
• Compare 7 and -2: Swap them → [1, 2, -3, 6, -2, 7, 1, -5, 9, 12]
• Compare 7 and 1: Swap them → [1, 2, -3, 6, -2, 1, 7, -5, 9, 12]
• Compare 7 and -5: Swap them → [1, 2, -3, 6, -2, 1, -5, 7, 9, 12]
• Compare 7 and 9: No swap → [1, 2, -3, 6, -2, 1, -5, 7, 9, 12]
• Compare 9 and 12: No swap → [1, 2, -3, 6, -2, 1, -5, 7, 9, 12]

Pass 3:

• Compare 1 and 2: No swap → [1, 2, -3, 6, -2, 1, -5, 7, 9, 12]
• Compare 2 and -3: Swap them → [1, -3, 2, 6, -2, 1, -5, 7, 9, 12]
• Compare 2 and 6: No swap → [1, -3, 2, 6, -2, 1, -5, 7, 9, 12]
• Compare 6 and -2: Swap them → [1, -3, 2, -2, 6, 1, -5, 7, 9, 12]
• Compare 6 and 1: Swap them → [1, -3, 2, -2, 1, 6, -5, 7, 9, 12]
• Compare 6 and -5: Swap them → [1, -3, 2, -2, 1, -5, 6, 7, 9, 12]
• Compare 6 and 7: No swap → [1, -3, 2, -2, 1, -5, 6, 7, 9, 12]
• Compare 7 and 9: No swap → [1, -3, 2, -2, 1, -5, 6, 7, 9, 12]

Passes 4 through 9: No more swaps are needed as the array is already sorted.

The final sorted array is: [1, -3, -2, -5, 1, 2, 6, 7, 9, 12]

Idea to Solve

Bubble Sort works by repeatedly iterating through the array, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until the entire array is sorted.

Pseudocode

procedure bubbleSort(A : list of sortable items)
        n = length(A)
        repeat
            swapped = false
            for i = 1 to n-1
                if A[i-1] > A[i]
                    swap A[i-1] and A[i]
                    swapped = true
                end if
            end for
        until not swapped
    end procedure

Algorithm Explanation

1. Start by initializing a flag swapped to false.
2. Iterate through the array using a loop from index 1 to n-1.
3. If the element at index i-1 is greater than the element at index i, swap them and set swapped to true.
4. After the inner loop completes, if swapped is still false, it means no swaps were performed, and the array is already sorted. In this case, exit the loop.
5. Repeat steps 2-4 until no swaps are performed in a full pass through the array.

Code Solution

1) Bubble sort in java 2) Bubble sort in c++ 3) Bubble sort in c 4) Bubble sort in c# 5) Bubble sort in vb.net 6) Bubble sort in php 7) Bubble sort in node js 8) Bubble sort in typescript 9) Bubble sort in python 10) Bubble sort in ruby 11) Bubble sort in scala 12) Bubble sort in swift 13) Bubble sort in kotlin 14) Bubble sort in golang

Time Complexity

The worst-case time complexity of Bubble Sort is O(n^2), where n is the number of elements in the array. This is because, in the worst case, you might need to perform n-1 comparisons in the first pass, n-2 in the second, and so on, resulting in (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 comparisons. The best-case time complexity is O(n) when the array is already sorted.

This article provides a simple explanation of the Bubble Sort algorithm, its working principle, and a step-by-step example. It also includes the Pseudocode and a brief analysis of its time complexity. Bubble Sort, although not very efficient for large arrays, is easy to understand and implement, making it a good introductory sorting algorithm.