# Bubble Sort in Python

## Sorting – Bubble Sort in Python🫧

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It’s often one of the first sorting algorithms taught to beginners due to its straightforward nature, making it an excellent starting point for understanding sorting algorithms.

## What is Bubble Sort in Python?

Bubble Sort is a simple sorting algorithm used to arrange elements in a list or array in a specific order, typically ascending or descending. It’s called “Bubble Sort” because smaller (or larger) elements “bubble up” to their correct positions during the sorting process.

## Working of Bubble Sort in Python

Let us try to sort the array using Bubble Sort in ascending order :

### Sorting is repeating at each step until all the unsorted elements is placed at its right position.

##### Algorithm for Bubble Sort in Python

Following are the steps used for sorting of elements in Bubble Sort:

• Step 1: Start at the beginning of the list.
• Step 2: Compare adjacent elements in pairs. If the current element is greater than the next, swap them.
• Step 3: Continue comparing and swapping for each pair, moving through the list.
• Step 4: After each pass, the largest element settles at the end.
• Step 5: Repeat steps 1-5 for one less element in the list on each pass.
• Step 7: Repeat until no swaps happen in a pass or you reach the end.
• Step 8: The list is sorted when no swaps occur, and the algorithm terminates.
##### Time and Space Complexity for Bubble Sort in Python

The time and space complexity of Bubble Sort in Python is as follows:

Time Complexity:

• Worst-case time complexity: O(n^2) – This occurs when the input list is in reverse order, and Bubble Sort has to make maximum comparisons and swaps.
• Average-case time complexity: O(n^2) – On average, Bubble Sort also requires n^2 comparisons and swaps.
• Best-case time complexity: O(n) – The best-case scenario happens when the input list is already sorted. In this case, Bubble Sort only needs to perform n-1 comparisons without any swaps.

Space Complexity:

• Bubble Sort has a space complexity of O(1) because it sorts the elements in-place without requiring additional memory allocation that scales with the input size. Regardless of the size of the input list, Bubble Sort uses a constant amount of extra memory for temporary variables.
##### Implementation of Bubble Sort in Python
```def bubble_sort(arr):
n = len(arr)

# Traverse through all elements in the list
for i in range(n):
# Flag to optimize the algorithm
swapped = False

# Last i elements are already in place, so we don't need to check them
for j in range(0, n-i-1):
# If the element found is greater than the next element, swap them
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
swapped = True  # Set the swapped flag to True

# If no two elements were swapped in the inner loop, the list is sorted
if not swapped:
break

# Example usage:
if __name__ == "__main__":
my_list = [64, 34, 25, 12, 22, 11, 90]
print("Original list:", my_list)

bubble_sort(my_list)

print("Sorted list:", my_list)

```

### Output :

```Original list: [64, 34, 25, 12, 22, 11, 90]
Sorted list: [11, 12, 22, 25, 34, 64, 90]
```
##### Explanation

The provided Python code implements the Bubble Sort algorithm to sort a list of numbers. It iterates through the list, comparing adjacent elements, and swapping them if they’re out of order. This process repeats until no more swaps are needed. Finally, it prints the sorted list.

##### To Wrap It Up:

Bubble Sort is a straightforward but relatively inefficient sorting algorithm in Python. While it’s useful for educational purposes and small datasets, its time complexity of O(n^2) makes it impractical for large lists. For practical applications, more efficient algorithms like Quick Sort or Merge Sort are preferred due to their better performance.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Question 1.

What is the time complexity of Bubble Sort?

In the worst and average cases, Bubble Sort has a time complexity of O(n^2), where ‘n’ is the number of elements in the list. This makes it inefficient for large datasets.

Question 2.

When is Bubble Sort a good choice?

Bubble Sort can be a reasonable choice for educational purposes to understand sorting algorithms. It’s also suitable for small datasets or nearly sorted data where its simplicity may outweigh its performance limitations.

Question 3.

Is Bubble Sort stable?

Yes, Bubble Sort is a stable sorting algorithm, which means that equal elements retain their relative order after sorting.

Question 4.

Is Bubble Sort commonly used in real-world software development?

No, Bubble Sort is rarely used in real-world software development due to its inefficiency for larger datasets. More advanced sorting algorithms are preferred for performance reasons.

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others