Bubble Sort in Java (With Intuition + Dry run + Code)

Introduction:
Sorting is the process of arranging items systematically, usually in ascending or descending order, based on some criterion. It's a fundamental concept in computer science and mathematics, as well as in everyday life.

Why Sorting?
Sorting plays a crucial role in various computing tasks:

Efficient Searching: Sorted data structures enable faster searching algorithms like binary search. Imagine finding a specific name in a phonebook: it's much quicker if the names are listed alphabetically.

Data Analysis and Visualization: Sorting helps analyze trends and patterns in data. For example, sorting sales figures by product allows you to identify best-sellers.

Data Merging: When combining data from multiple sources, sorting ensures consistent ordering and avoids duplicates.

Algorithmic Efficiency: Many algorithms, including searching, merging, and joining, become significantly more efficient when dealing with sorted data.

User Experience: Presenting data in a sorted manner often improves user experience by making it easier to locate and understand information.

Today, we will cover Bubble sort which is the most basic sorting algorithm. Let's jump in:

Why the name bubble right?

Bubble Sort gets its name from the way smaller elements "bubble" to the top of the list, much like air bubbles rising to the surface in water. In this sorting algorithm, adjacent elements are compared and swapped if they are in the wrong order. This process is repeated for each pair of adjacent elements in the list until the entire list is sorted.

During each iteration, the largest unsorted element "bubbles up" to its correct position at the end of the list. This process resembles bubbles rising to the surface, hence the name "Bubble Sort."

Algorithm:

1. Start with the first element (index 0) and compare it with the next element (index 1).
2. If the first element is greater than the second element, swap them.
3. Move to the next pair of elements (index 1 and index 2) and compare them. Again, swap if necessary.
4. Continue this process until you reach the end of the list.
5. After the first pass, the largest element will be at the last position.
6. Repeat steps 1-5 for the remaining elements (excluding the last sorted element) until the entire list is sorted.

I will show the working of Bubble sort but make sure to dry run using pen & paper📝

 java
import java.util.*;

public class BubbleSort {

   public static void main(String[] args) {

      Scanner sc = new Scanner(System.in);

      int len = sc.nextInt();

       int arr[] = new int[len];

       for(int i=0; i<len; i++){
          arr[i] = sc.nextInt();
       }

        //int arr[] = {4, 8, 2, 7, 9, 2};

        //int len = arr.length;

        for(int i=len-1; i>0; --i) {
            int swapped = 0;
            for(int j=0; j<i; j++) {
                if(arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        for(int i=0; i<len; i++) {
            System.out.print(arr[i]+" ");
        }
    }

}

Time complexity:

• Worst-case: O(n^2)
• Best-case: O(n)

Space complexity: O(1)

Wrapping Up:

Now, congrats, you've learned bubble sort 🥳👏

Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7