# Bubble Sort

## Bubble Sort

Bubble Sort is a comparison-based sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. The algorithm continues to iterate until the list is sorted.

Here is the step-by-step process of Bubble Sort:

Start at the beginning of the list.

Compare the first element with the second element. If the first element is greater than the second element, swap them.

Move to the next pair of adjacent elements and perform the same comparison and swap if necessary.

Continue this process until the end of the list is reached. By the end of the first pass, the largest element will be in its correct position at the end of the list.

Repeat steps 1-4 for the remaining elements of the list, excluding the last element that is already sorted.

Continue this process until the entire list is sorted.

The algorithm gets its name from the way smaller elements "bubble" to the top of the list with each pass. Bubble Sort has a worst-case and average time complexity of O(n^2), where n is the number of elements in the list. It is not considered an efficient sorting algorithm for large data sets but can be useful for small or nearly sorted lists due to its simplicity and ease of implementation.

Although Bubble Sort is not efficient compared to other sorting algorithms, it has some advantages. It is easy to understand and implement, requires minimal additional memory, and performs well for small input sizes or partially sorted lists. However, for larger data sets, other sorting algorithms like Quick Sort or Merge Sort are generally preferred.

### Bubble Sort Code in Python

Here's an implementation of the Bubble Sort algorithm in Python:

def bubble_sort(arr):

n = len(arr)

# Traverse through all array elements

for i in range(n):

# Last i elements are already in place

for j in range(0, n-i-1):

# Swap if the element found is greater than the next element

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage:

array = [5, 2, 8, 1, 9, 3]

bubble_sort(array)

print("Sorted array:", array)

# Optimized Bubble Sort

An optimized version of Bubble Sort is called "Optimized Bubble Sort" or "Flagged Bubble Sort". It improves the algorithm's efficiency by introducing a flag that keeps track of whether any swaps were made in a pass. If no swaps are made, it means the array is already sorted, and the algorithm can terminate early.

Here's the code for the optimized Bubble Sort in Python:

def bubble_sort(arr):

n = len(arr)

# Traverse through all array elements

for i in range(n):

# Initialize a flag to track if any swaps were made in the current pass

swapped = False

# Last i elements are already in place

for j in range(0, n-i-1):

# Swap if the element found is greater than the next element

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]

swapped = True

# If no swaps were made in the current pass, the array is already sorted

if not swapped:

break

# Example usage:

array = [5, 2, 8, 1, 9, 3]

bubble_sort(array)

print("Sorted array:", array)

In this optimized version, the swapped flag is initially set to False. After each pass, if no swaps were made (i.e., swapped remains False), it means the array is sorted and the algorithm can terminate early by breaking out of the outer loop.