Bubble sortÂ
- It is a very simple sort.Â
- It has comparison-based sorting.Â
- We will compare the value of index 1 of the input with the value of index 2, and see which value is smaller. Whatever value is small, we will use in index 1 and whatever value will be big, we will use it in index 2.Â
- After that, we will compare the value of index 2 with the value of index 3, and in that also, we will put the small value in index 2 and we will keep the large value in index 3. Look at an example.
Input – n = 7
Iteration 1
The output of Iteration 1 is not fully sorted so we will do Iteration 2. But one thing to see in this is that, the largest number in the array will come in the last. 18 number was the largest number in the input, so in iteration 1, index of 18 became 7, meaning in the last index.
Iteration 2
Index 6 and index 7 were not compared in iteration 2 because when we  did iteration 1, we  put  the largest number of arrays in index 7  that is the last index, then index 7  is already sorted| The output of iteration 2 is  also not fully sorted,  so we will do iteration 3, and in this, the number 12 which is the largest number in the unsorted array will come in the last index 6.
Iteration 3
In Iteration 3, we  will not compare index  5 and index 6 because  in iteration 2 we  have already placed the largest number 12  in index 6 (the last index of the unsorted array.
Now the output is fully sorted.
BubbleSort(Array[],x)
for x <- 1 to Array[Max Index Unsorted Values-1]
if(Array[x] > Array[x+1])
Swap(Array[x], Array[x+1])
If swapping done, then start with statement 1
BubbleSort(Array[],x)
- for x <- 1 to Array[Max Index Unsorted Values – 1]
In the unsorted array we  will take a variable x and its value will  go from 1  to maximum index – 1.
- if(Array[x] > Array[x+1])
Now we will  compare the value of x+1 with  the value of x  and if the value of Array[x] is greater than Array[x+1] then we  will go to statement 3. If small, we’ll run for loop again.
- Swap(Array[x], Array[x+1])
If the value of Array[x] is greater than Array[x+1], we will swap.
- If swapping done, then start with statement 1
If we have swapped, we need another iteration, Because if the array was sorted in this iteration, we would not need swapping, and if  it is not sorted, then we need one more iteration.
.
Program of Bubble Sort in C
// Write a program for Bubble Sort
// COMPUTER GEEK – compgeek.co.in
// Write a program for Bubble Sort
#include <iostream>
using namespace std;
int main()
{
   int x, size, temp, flag, Array[100];
   // Input Array declaration
   cout << “Enter the size of input array : “;
   cin >> size;
   // Input Array initialization
   cout << “Enter the ” << size << ” items of array : “;
   for(x = 0; x < size; x++)
  {
       cin >> Array[x];
   }
   // Bubble Sort startsÂ
   do
  {
       flag = 0;
       for(x = 0; x < size – 1; x++)  // x -> index 1 to index max-1
    {
           if(Array[x] > Array[x + 1])  // true then swap
      {
               temp = Array[x];
               Array[x] = Array[x + 1];
               Array[x + 1] = temp;
               flag = 1; // if swapping is done, then flag will be 1
           }
       }
   } while(flag == 1); // if flag = 1, then you need another iteration
   // Sorted Array after bubble sort
   cout << “The sorted array is : “;
   for(x = 0; x < size; x++)
  {
       cout << Array[x] << ” “;
   }
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Bubble Sort
Â
import java.util.Scanner;
Â
public class BubbleSort
{
   public static void main(String[] args)
  {
       Scanner scanner = new Scanner(System.in);
       int x, size, temp, flag;
       int[] Array = new int[100];
Â
       // Input Array declaration
       System.out.print(“Enter the size of input array : “);
       size = scanner.nextInt();
Â
       // Input Array initialization
       System.out.print(“Enter the ” + size + ” items of array : “);
       for (x = 0; x < size; x++)
    {
           Array[x] = scanner.nextInt();
       }
Â
       // Bubble Sort starts
       do
    {
           flag = 0;
           for (x = 0; x < size – 1; x++)    // x -> index 1 to index max-1
      {Â
               if (Array[x] > Array[x + 1])   // true then swap
        {
                   temp = Array[x];
                   Array[x] = Array[x + 1];
                   Array[x + 1] = temp;
                   flag = 1; // if swapping is done, then flag will be 1
               }
           }
       } while (flag == 1); // if flag = 1, then you need another iteration
Â
       // Sorted Array after bubble sort
       System.out.print(“The sorted array is : “);
       for (x = 0; x < size; x++)
    {
           System.out.print(Array[x] + ” “);
       }
   }
}
# COMPUTER GEEK – compgeek.co.in
# Write a program for Bubble Sort
Â
def main():
   size = int(input(“Enter the size of input array: “))
   array = list(map(int, input(f”Enter the {size} items of array: “).split()))
Â
   # Bubble Sort starts
   flag = True
   while flag:
       flag = False
       for x in range(size – 1): # x -> index 1 to index max-1
           if array[x] > array[x + 1]: # true then swap
               array[x], array[x + 1] = array[x + 1], array[x]
               flag = True # if swapping is done, then flag will be True
Â
   # Sorted Array after bubble sort
   print(“The sorted array is:”, *array)
Â
Â
if __name__ == “__main__”:
   main()
Time Complexity of Bubble Sort
Input array size = n
The time complexity in the best case will be O(n).
Reason – In the best case, if all the values in the unsorted input array are already sorted, then the compiler will go to loop only once.
In the worst case, the time complexity will be O(n2).
Reason – in the worst case, all values in the unsorted input array will be non-decreasing. For loop will have n number of operations, and do while loop number of operations will also be n. Since the loops are nested loops, then time complexity will be O(n*n).Â
In the average case, the time complexity will be O(n2).
As in the worst case, the same thing happen here, the number of operations of the for loop will be n, and the number of operations of the do while loop will also be n – constant. Since these two loops are nested loops then time complexity will be n*(n – constant).
Â
Space Complexity of Bubble Sort
Space complexity will be O(1) because we need an extra memory space to swap.
Â
Optimized bubble sort
If the array is completely sorted after some iterations, but we still need to complete all of the iterations as the formula demands. We are putting in more effort, which is useless.
It can be solved by inserting a flag variable without any further effort.Â
If flag = 0, it means that swapping did not occur. If swapping did not occur, there is no need in comparing array elements because the array is completely sorted. If we swap, the flag = 1, indicating that the array may not be completely sorted and that we must run the for loop again.
With this, we will not have to run for loop many times. The number of operations will be reduced and time complexity will also decrease in optimized bubble sort.
Â
Advantage of Bubble Sort
- This is a stable sort.
- It is also an in-place sort.
- The space complexity of this sort is also O(1).
Test Yourself
Q1- Can Bubble Sort handle duplicate elements properly?
Yes, Bubble Sort can handle duplicate elements properly and maintains their original order in the sorted output. It is a stable sorting algorithm.
Q2- What is the main disadvantage of the Bubble Sort algorithm?
The main disadvantage of Bubble Sort is its relatively high time complexity, especially in the worst and average-case scenarios. It has a time complexity of O(n^2), making it inefficient for large datasets.
Q3- Describe the flag variable used in the optimized Bubble Sort.
The flag variable is used in the optimized version of Bubble Sort to track whether any swaps were performed during a pass through the array. If no swaps are made, it means that the array is already sorted, and the algorithm can terminate early.
Q4- Is Bubble Sort an in-place sorting algorithm?
Yes, Bubble Sort is an in-place sorting algorithm. It sorts the elements within the same array without requiring additional memory proportional to the input size.
Q5- How does Bubble Sort perform in a scenario where the input array is reverse-sorted?
In a scenario where the input array is reverse-sorted, Bubble Sort will have its worst-case time complexity of O(n^2). It will require multiple passes through the array, repeatedly swapping adjacent elements until it is fully sorted.
Q6- How does Bubble Sort compare to other sorting algorithms in terms of efficiency?
Compared to more advanced sorting algorithms like Merge Sort or Quick Sort, Bubble Sort is less efficient. It has a higher time complexity in most scenarios, making it suitable for small datasets but impractical for large ones.
Q7- What is the main disadvantage of Bubble Sort?
Unstable sorting
High time complexity
Excessive memory usage
Difficulty in implementation
Ans – (2) High time complexity
Explanation – The main disadvantage of Bubble Sort is its relatively high time complexity, especially for larger datasets.
Â
Q8- Which property does Bubble Sort exhibit when handling duplicate elements?
In-place sorting
Unstable sorting
Stable sorting
Data-sensitive sorting
Ans – (3) Stable sorting
Explanation: Bubble Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements in the sorted output.
