# 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.

## 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.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.