A Simple Guide to Bubble Sort Technique

Bubble sort is simple comparison based sorting technique.

Steps:

1. Compare each pair of adjacent elements.

2. If current element is greater than next element, swap them.

3. Continue this process for the entire array.

4. With each iteration, the largest unsorted element moves to its correct position at the end of the array.

5. Repeat the above steps for the remaining elements.

Java code for Bubble Sort:

class Bubble_sort{
    public static void main(){
        int arr[]={2,1,0,4,5,7};
        solution(arr);
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+" ");
        }
    }

    private static void Solution(int arr[]){
        boolean swapped=true;
        for(int i=0; i<arr.length; i++){
            for(int j=1; j<arr.length-i; j++){
                if(arr[j-1] > arr[j]){
                    int temp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                    swapped=false;
                }
            }
            if(!swapped){
                break;
            }
        }
    }
}

Time Complexity:

• Best Case: O(N) [N=length of array]

  ⭐

  If the array is already sorted, the swapped flag prevents unnecessary iterations and leading to linear time complexity.

• Average Case: O(N²)

  ⭐

  On average, the algorithm compares and swaps elements multiple times.

• Worst Case: O(N²)

  ⭐

  The worst case scenario occurs when the array is sorted in reverse order.

Conclusion:

The use of swapped flag helps to optimize the performance when array is already sorted or becomes sorted before all iterations are complete. Without this flag, the time complexity would always be O(N²), even for sorted arrays.

Bubble Sort is not suitable for large datasets due to its quadratic time complexity. More efficient algorithms like Merge Sort, Quick Sort, or Heap Sort are typically used for larger data which will be discussed later.