## Data Structure Tutorial Index

This tutorial explains Bubble Sort, a fundamental sorting algorithm in computer science. It demonstrates the process of swapping adjacent elements to create a sorted list, making it an ideal starting point for beginners.

## Understanding the Bubble Sort Algorithm

The Bubble Sort algorithm in computer science is a basic sorting technique for sorting lists or arrays in a specific order, typically ascending or descending. It works by repeatedly swapping adjacent elements if they are in the incorrect order. This process repeats until the entire list is sorted. Despite its simplicity, Bubble Sort is not the most efficient for large datasets but provides a foundational understanding of sorting algorithms.

## Why It's Named Bubble Sort

Bubble Sort is named after the way elements move to their correct position in the list. In each iteration, the largest (or smallest, depending on the sorting order) unsorted element rises to its correct position in the array. This process is similar to bubbles rising to the surface of water.

## How Bubble Sort Works

Let's assume you have an unsorted array - `[5, 3, 8, 2, 1]`, and want to sort it in ascending order. Bubble sort works by repeatedly iterating through the array, comparing adjacent elements, and swapping them if they are in the incorrect order. This process is repeated until the array is fully sorted. For our example, the sorting process would involve several passes through the array, each time moving unsorted elements closer to their final position until achieving the sorted array - `[1, 2, 3, 5, 8]`.

Pass Comparisons and Actions Resulting Array
1 Compare 5 and 3, swap `[3, 5, 8, 2, 1]`
1 Compare 5 and 8, no swap `[3, 5, 8, 2, 1]`
1 Compare 8 and 2, swap `[3, 5, 2, 8, 1]`
1 Compare 8 and 1, swap `[3, 5, 2, 1, 8]`
After the first pass, the largest number (`8`) has "bubbled up" to its correct position at the end of the array.
2 Compare 3 and 5, no swap `[3, 5, 2, 1, 8]`
2 Compare 5 and 2, swap `[3, 2, 5, 1, 8]`
2 Compare 5 and 1, swap `[3, 2, 1, 5, 8]`
After the second pass, the next largest number (`5`) is now in its correct position before the already sorted `8`.
3 Compare 3 and 2, swap `[2, 3, 1, 5, 8]`
3 Compare 3 and 1, swap `[2, 1, 3, 5, 8]`
At this point, `5` and `8` are correctly positioned, and we're left with a partially sorted beginning of the array.
4 Compare 2 and 1, swap `[1, 2, 3, 5, 8]`
After the fourth pass, all elements are now in their correct positions, and the array is sorted in ascending order.

## Implementation Examples

### C++ Example

Implementing Bubble Sort in C++ is straightforward. The following code snippet demonstrates this process:

Example:

``````#include <iostream>
using namespace std;

// Function to perform bubble sort on the array
void bubbleSort(int arr[], int n) {
// Loop for each element of the array except the last one
for(int i = 0; i < n-1; i++) {
// Inner loop for comparison and swapping
// Goes up to the part of the array that hasn't been sorted yet
for(int j = 0; j < n-i-1; j++) {
// If the current element is greater than the next one, swap them
if(arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}
}

int main() {
int arr[] = {5, 3, 8, 2, 1}; // Initial array
int n = sizeof(arr)/sizeof(arr[0]); // Calculate the number of elements in the array
bubbleSort(arr, n); // Call the bubbleSort function
cout << "Sorted array: "; // Display the sorted array
for(int i = 0; i < n; i++) {
cout << arr[i] << " "; // Print each element of the sorted array
}
return 0;
}``````

Output:

``Sorted array: 1 2 3 5 8``

### Python Example

In Python, the Bubble Sort algorithm can be implemented as follows:

Example:

``````# Function to perform bubble sort on the array
def bubbleSort(arr):
n = len(arr) # Get the number of elements in the array
# Outer loop for traversing through each element of the array
for i in range(n):
# Inner loop for comparing adjacent elements
# Goes up to the part of the array that hasn't been sorted yet
for j in range(0, n-i-1):
# If the current element is greater than the next one, swap them
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j] # Perform the swap

# Sample array of characters
arr = ['z', 'e', 'b', 'r', 'a']
bubbleSort(arr) # Call the bubbleSort function to sort the array
print("Sorted array is:", arr) # Print the sorted array
``````

Output:

``Sorted array is: ['a', 'b', 'e', 'r', 'z']``

### Java Example

Here's the Java code for implementing the Bubble Sort algorithm:

Example:

``````public class BubbleSort {

// Method to perform bubble sort
public 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++) {
// Swap if the element found is greater than the next element
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// IF no two elements were swapped by inner loop, then break
if (!swapped)
break;
}
}

// Main method to test the bubbleSort method
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.print("Sorted array is: ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
``````

Output:

``Sorted array is: 11 12 22 25 34 64 90``

## Time Complexity

The time complexity of Bubble Sort is `O(n^2)` in both average and worst-case scenarios, which means the time taken to sort the elements increases quadratically as the number of elements (`n`) grows. This complexity makes Bubble Sort inefficient for sorting large datasets compared to more advanced algorithms.

## Conclusion

Bubble Sort is a simple yet effective sorting algorithm that is an excellent starting point for understanding how sorting works. Although it may not be the most efficient for practical applications, learning Bubble Sort is fundamental to grasping more complex sorting techniques. It emphasizes essential concepts like iteration and swapping, critical to many computer science algorithms.