Bubble Sort Simplified
Tags: algorithms, webdev, beginners
Published: 2023-03-31 11:01:15


In computer science, sorting is a fundamental job that is essential to many different applications, including database administration and image processing. Sorting is the act of arranging a collection of objects in a certain order, such as alphabetical or numerical order, so that they may be conveniently searched or processed.

There are several methods for sorting data, each with its own set of advantages and disadvantages. Bubble sort is one of the most basic and well-known sorting algorithms. Bubble sort is a simple algorithm that beginners may readily understand and is frequently used as an introduction to sorting algorithms.

In this article, we'll look into bubble sort in further detail, including how it works, its advantages and disadvantages, as well as practice guidelines for using and improving it. Understanding bubble sort is a vital step in mastering sorting algorithms and increasing your coding abilities, whether you're a new programmer or an expert developer. Now let's get started and discover the world of bubble sorting!

### How Bubble Sort Works
Bubble sort is a basic comparison-based sorting algorithm that operates by repeatedly exchanging nearby components that are in the wrong order. Larger items "bubble" to the top of the list with each run, giving rise to the algorithm's name. Below is a step-by-step walkthrough of bubble sort implementation.
Below are the steps to follow:
- Use two for loops to iterate through the input array.
- The outer loop runs from `i = 0` to `i = n - 1`.
- The inner loop runs from `j = 0` to `j = n - i - 1`;
- For every `j`, compare `arr[j]` and `arr[j + 1]`. If `arr[j] > arr[j + 1]`, then swap them or else move forward.


### Python Implementation
```
1. def bubbleSort(arr):
2.     for i in range(len(arr)):
3.         for j in range(len(arr)-i-1):
4.             if arr[j] > arr[j+1]:
5.                arr[j], arr[j+1] = arr[j+1], arr[j]
6.    return arr
7. 
8. bubbleSort([13, 4, 9, 5, 3, 16, 12]) # [3, 4, 5, 9, 12, 13, 16]
```


In the implementation above, we traverse through the array on different passes. On each pass, we compare the current element and the one immediately after it. If the current element is bigger than the one on the right, we swap them(line 5).

### Time Complexity
Best - O(n)
Worst - O(n2)
Average - O(n2)
Space Complexity - O(1)
Stability - Yes

### Pros and Cons of Bubble Sort
#### Pros:
- **Simple**: Bubble sort is one of the simplest sorting algorithms to understand and implement.

- **In-place sorting**: Bubble sort only requires a constant amount of additional memory space to sort a list, making it an "in-place" sorting algorithm.

- **Stable**: Bubble sort is a "stable" sorting algorithm, meaning that it preserves the relative order of equal elements in the list.

#### Cons:
- **Inefficient for large lists**: Bubble sort has a time complexity of O(n²), meaning that its performance becomes increasingly slow as the size of the list grows. For very large lists, bubble sort can become impractical.

- **Inefficient for partially sorted lists**: Bubble sort still needs to compare every element to every other element, even if the list is already partially sorted. This can lead to unnecessary comparisons and swaps.

- **Not the most efficient sorting algorithm**: There are other sorting algorithms, such as quicksort and mergesort, that have better time complexity than bubble sort and can be more efficient for large lists.

## Conclusion
Bubble sort is a simple, easy-to-understand sorting algorithm that can be useful for small lists or as a learning exercise for understanding sorting algorithms. However, it is not the most efficient sorting algorithm for large lists or partially sorted lists. For those cases, it may be more efficient to use a different sorting algorithm that has better time complexity.


Don't forget to leave a like or comment.

❤️❤️❤️

[Resume](https://docs.google.com/document/d/1Lcr8tSfNozE9MLOKCDF8CwvZH0g7LWJSq9vu3Rdj0_U/edit?usp=drivesdk) [Portfolio](https://valentinesamuel.vercel.app/) [Twitter](https://twitter.com/frontend_val) [GitHub](https://github.com/valentinesamuel) [LinkedIn](https://www.linkedin.com/in/samuel-val/)