Bubble Sort

Introduction

Bubble Sort is a simple comparison based algorithm that compares adjacent elements and swap them if they are in wrong order. This process is repeated until the list is fully sorted.

Complexity

• Best Case Time Complexity: O(n) (when the array is already sorted)
• Average Case Time Complexity: O(n²)
• Worst Case Time Complexity: O(n²)
• Space Complexity: O(1) (in-place sorting)

Algorithm Steps

• Start at the beginning of the array.
• Compare the first two adjacent elements:
  • If the first is greater than the second, swap them.
• Move to the next adjacent pair and repeat the comparison and swapping.
• Continue until the end of the array. After each pass, the largest element bubbles up to its correct position.
• Repeat the process for the remaining elements, ignoring the last sorted ones, until no swaps are needed.

Example

Let's take an example of an array whose elements are : [5][3][8][4][2]

Pass 1:

• [5][3][8][4][2], compare 5 and 3. Since 5>3 => swap(5,3)
• [3][5][8][4][2], now compare 5 and 8. Since 5<8 => no swap(5,8)
• [3][5][8][4][2], now compare 8 and 4. Since 8>4 => swap(8,4)
• [3][5][4][8][2], now compare 8 and 2. Since 8>2 => swap(8,2)
• [3][5][4][2][8], the largest element [8] is now in correct place.
  Now for next pass, we can ignore the last element (i.e. 8) as it is already sorted.

Pass 2:

• [3][5][4][2], compare 3 and 5. Since 3<5 => no swap(3,5)
• [3][5][4][2], compare 5 and 4. Since 5>4 => swap(5,4)
• [3][4][5][2], compare 5 and 2. Since 5>2 => swap(5,2)
• [3][4][2][5], the largest element [5] is now in correct place.
  Now for next pass, we can ignore the last element (i.e. 5) as it is already sorted.

Pass 3:

• [3][4][2], compare 3 and 4. Since 3<4 => no swap(3,4)
• [3][4][2], compare 4 and 2. Since 4>2 => swap(4,2)
• [3][2][4], the largest element [4] is now in correct place.
  Now for next pass, we can ignore the last element (i.e. 4) as it is already sorted.

Pass 4:

• [3][2], compare 3 and 2. Since 3>2 => swap(3,2)
• [2][3], all the elements are now in sorted form.

Sorted array: [2][3][4][5][8]

Key Observations

• After each pass, the largest unsorted element moves to its correct position.
• Fewer comparisons are needed in each subsequent pass.
• If no swaps occur in a pass, the array is already sorted.

Advantages

• Bubble sort is easy to understand and implement, making it a good introductory algorithm for learning about sorting techniques.
• It sorts the array in place without requiring extra memory, making it space-efficient (O(1) space complexity).
• If the array is already sorted or nearly sorted, bubble sort performs very efficiently. The algorithm can detect this and terminate early, improving performance in such cases. The best case time complexity is O(n).
• Bubble sort is stable, meaning that it does not change the relative order of equal elements in the array. This can be useful in situations where stability is required, such as when sorting a list of records based on a secondary attribute.

Disadvantages

• Bubble sort has a worst-case and average-case time complexity of O(n²). For large arrays or datasets, this makes it one of the slowest sorting algorithms and impractical for performance-critical applications.
• Even if the array becomes partially sorted during the process, bubble sort will continue making redundant comparisons, leading to unnecessary operations.
• As the number of elements (n) increases, the number of operations grows rapidly. For an array of size n, bubble sort might require up to n(n-1)/2 comparisons and swaps, making it inefficient for large datasets.

Code in C:

#include<stdio.h>

void main(){
    int arr[100];  // consider the size of array 100
    int n;
    printf("enter the size of array\n");
    scanf("%d",&n);
    
    printf("enter the array elements\n");
    for(int i=0; i<n; i++{
        scanf("%d",&arr[i]);
    }
 
    // unsorted array--
    printf("unsorted array is :\n");
    for(int i=0; i<n; i++{
        printf("%d ",arr[i]);
    }

    // Sorting the elements using bubble sort-
    for(int i=0; i<n-1; i++){
        for(int j=0; j<n-1-i; j++){
            if(arr[j]>arr[j+1]){
               int temp=arr[j];    //swap the elements
               arr[j]=arr[j+1];
               arr[j+1]=temp; 
            }
         }
     }

    // sorted array--
    printf("sorted array is : ");
    for(int i=0; i<n; i++{
        printf("%d ",arr[i]);
    }

}

Code in C++:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cout<<"enter the size of array"<<endl;
    cin>>n;
    int arr[n];
    cout<<"enter the array elements"<<endl;
    for(int i=0;i<n;i++)
    cin>>arr[i];
    cout<<"unsorted array is : ";
    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    //bubble sort method
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1-i;j++){
            if(arr[j]>arr[j+1]){
                int temp=arr[j]; //swap the elements
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    cout<<endl<<"sorted array is : ";
    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    return 0;
}

Code in JAVA:

import java.util.Scanner;
class solution{
    public static void main(String[] args){
         Scanner sc = new Scanner(System.in);
         System.out.println("enter the size of array");
         int n = sc.nextInt();
         int[] arr = new int[n];

         System.out.println("enter the array elements");
         for(int i = 0; i<n; i++){
              arr[i] = sc.nextInt();
         }
      
         // printing the unsortd array

         System.out.print("unsorted array is: ");
         for(int i = 0; i<n; i++){
             System.out.print(arr[i]+" ");
         }
         
         // Sorting the elements using bubble sort-
         for(int i=0; i<n-1; i++){
              for(int j=0; j<n-1-i; j++){
                    if(arr[j]>arr[j+1]){
                         int temp=arr[j];    //swap the elements
                         arr[j]=arr[j+1];
                         arr[j+1]=temp; 
                    }
              }
         }
         
         // printing the Sorted Array
         System.out.print("sorted array is: ");
         for(int i = 0; i<n; i++){
             System.out.print(arr[i]+" ");
         }
    }
}

Output

enter the size of array
5
enter the array elements
5 3 8 4 2
unsorted array is : 5 3 8 4 2 
sorted array is : 2 3 4 5 8