## Program Bubble Sort

#### Definition & Explanation

- Bubble Sort is a simple sorting algorithm that repeatedly steps through the list (array), compares adjacent elements, and swaps them if they are in the wrong order.
- The pass through the list is repeated until the entire list is sorted.

**Example:Input: Array: [8, 5, 3, 1, 9, 6, 0, 7, 4, 2]Output:**

`Sorted Array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]`

**Procedure:**

- Start with the first element of the array.
- Compare it with the next element.
- If the first element is greater than the second, swap them.
- Move to the next pair of elements and repeat the process until the end of the array is reached.
- After the first pass, the largest element is guaranteed to be at the end of the array.
- Repeat the process for the remaining elements, excluding the last one in each pass since it’s already sorted.

**Pseudocode**

procedure bubbleSort(A: list)

n = length(A)

for i from 0 to n-1

for j from 0 to n-1-i

if A[j] > A[j+1]

swap(A[j], A[j+1])

#### Method 1 :

```
#include <stdio.h>
void main() {
int a[] = {1, 44, 3, 2, 66, 0};
int n = sizeof(a) / sizeof(a[0]);
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
}
```

#### Output :

`0 1 2 3 44 66 `

#### Method 1 :

```
#include <iostream>
class HelloWorld {
public:
static void main() {
int a[] = {1, 44, 3, 2, 66, 0};
int n = sizeof(a) / sizeof(a[0]);
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) {
std::cout << a[i] << " ";
}
}
};
int main() {
HelloWorld::main();
return 0;
}
```

#### Output :

`0 1 2 3 44 66 `

#### Method 1 :

```
class HelloWorld {
public static void main(String[] args) {
int a[]={1,44,3,2,66,0};
int temp=0;
for (int i=0;i<a.length;i++){
for(int j=0;j<a.length-1-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
}
```

#### Output :

`0 1 2 3 44 66 `

#### Method 1 :

```
class HelloWorld:
@staticmethod
def main():
a = [1, 44, 3, 2, 66, 0]
for i in range(len(a)):
for j in range(len(a) - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
for i in a:
print(i, end=" ")
if __name__ == "__main__":
HelloWorld.main()
```

#### Output :

`0 1 2 3 44 66 `

**Example:**- Consider the array
`a = [1, 44, 3, 2, 66, 0]`

. - After the first pass, the largest element (66) is moved to the last position.
- After the second pass, the next largest element (44) is moved to the second-to-last position.
- The process continues until the entire array is sorted.

- Consider the array
**Time Complexity:**- Bubble Sort has a time complexity of O(n^2) in the worst and average cases, where n is the number of elements in the array.
- In the best-case scenario (when the array is already sorted), the time complexity is O(n).

**Space Complexity:**- Bubble Sort is an in-place sorting algorithm, meaning it doesn’t require additional memory to sort the array.

### Explanation:

Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order. This process of bubbling the largest (or smallest, depending on the sorting order) elements to the end of the array is repeated until the entire array is sorted. While simple, Bubble Sort is not the most efficient sorting algorithm, especially for large datasets, due to its quadratic time complexity. Other algorithms like Merge Sort or Quick Sort are often preferred for larger datasets.