Bubble Sort
- Bubble Sort is a simple
sorting algorithmthat repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. - This process is repeated until the array is sorted.
- After each pass, the largest unsorted element
“bubbles up” to its correct positionat the end of the array. It’s called “Bubble Sort” - As
smaller elementsslowly “bubble” to the top of the list.
Approach:
- Iterate through the
array multiple times. - In
each pass, compare adjacent elements. - If the
current elementis greater than the next one, swap them. - After each pass, the
largest unsorted elementbubbles up to its correct position at theend. - Use a
boolean flag(isSwapped) to track whether any swapping happened. - If
no swapsoccurred in a full pass, thearray is already sorted→ early exit (optimization). - Repeat this process for
n - 1passes (where n is the array length), or until no swaps are needed.
Time & Space Complexity:
Time Complexity: O(n) (Best Case) when array is already sorted (optimized with isSwapped).
Worst Case: O(n2) When array is in reverse order.
Space Complexity: O(1) In-place sorting, no extra space used.
Dry Run
Input: arr = [4, 5, 1, 3, 9]
Pass 1 (i = 0): j = 0 → [4, 5, 1, 3, 9] → 4 < 5 → no swap j = 1 → [4, 5, 1, 3, 9] → 5 > 1 → swap → [4, 1, 5, 3, 9] j = 2 → [4, 1, 5, 3, 9] → 5 > 3 → swap → [4, 1, 3, 5, 9] j = 3 → [4, 1, 3, 5, 9] → 5 < 9 → no swap Pass 2 (i = 1): j = 0 → [4, 1, 3, 5, 9] → 4 > 1 → swap → [1, 4, 3, 5, 9] j = 1 → [1, 4, 3, 5, 9] → 4 > 3 → swap → [1, 3, 4, 5, 9] j = 2 → [1, 3, 4, 5, 9] → 4 < 5 → no swap Pass 3 (i = 2): j = 0 → [1, 3, 4, 5, 9] → 1 < 3 → no swap j = 1 → [1, 3, 4, 5, 9] → 3 < 4 → no swap → No swaps → break
Output: [1, 3, 4, 5, 9]
let arr = [4,5,1,3,9]
function bubbleSort(arr){
let n = arr.length;
for(let i = 0; i < n-1; i++) {
let isSwapped = false;
for(let j = 0; j < n-1-i; j++) {
if(arr[j]>arr[j+1]) {
let temp=arr[j]
arr[j]=arr[j+1];
arr[j+1]=temp;
isSwapped=true;
}
}
if(!isSwapped)
break;
}
return arr;
}
let result = bubbleSort(arr)
console.log("Sorted array",result)
def bubbleSort(arr):
n = len(arr)
for i in range(n - 1):
is_swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
is_swapped = True
if not is_swapped:
break
return arr
arr = [4, 5, 1, 3, 9]
print("Sorted array:", bubbleSort(arr))
public class Solution {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean isSwapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSwapped = true;
}
}
if (!isSwapped) break;
}
}
public static void main(String[] args) {
int[] arr = {4, 5, 1, 3, 9};
bubbleSort(arr);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool isSwapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
isSwapped = true;
}
}
if (!isSwapped) break;
}
}
int main() {
int arr[] = {4, 5, 1, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}
#include <stdio.h>
#include <stdbool.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool isSwapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSwapped = true;
}
}
if (!isSwapped) break;
}
}
int main() {
int arr[] = {4, 5, 1, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
using System;
class Program
{
static int[] BubbleSort(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
{
bool isSwapped = false;
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSwapped = true;
}
}
if (!isSwapped)
break;
}
return arr;
}
static void Main(string[] args)
{
int[] arr = { 4, 5, 1, 3, 9 };
int[] result = BubbleSort(arr);
Console.WriteLine("Sorted array: " + string.Join(", ", result));
}
} 
