Bubble Sort

 

📚 What is Bubble Sort?

Bubble Sort is a simple sorting algorithm that:

  • Repeatedly compares adjacent elements

  • Swaps them if they are in the wrong order.

  • After each pass, the largest element  is placed to its correct position.

It’s called bubble sort because small elements "bubble" to the top of the list (start) with repeated swaps.

How Bubble Sort Works?

Imagine sorting [5, 1, 4, 2, 8]:

  1. Compare 5 and 1 → Swap → [1, 5, 4, 2, 8]

  2. Compare 5 and 4 → Swap → [1, 4, 5, 2, 8]

  3. Compare 5 and 2 → Swap → [1, 4, 2, 5, 8]

  4. Compare 5 and 8 → No swap.

✅ 8 is now in its correct position.

Repeat for the rest until sorted.

Bubble Sort Algorithm 

Algorithm: Bubble Sort

  1. Start from the first element (index 0).

  2. Compare the current element with the next element.

  3. If the current element is greater than the next element, swap them.

  4. Move to the next element and repeat steps 2–3 for the whole list.

  5. After each full pass, the last unsorted element is correctly placed.

  6. Repeat the entire process for the remaining unsorted part of the list.

  7. Stop when no more swaps are needed.

✍️ Pseudocode


BubbleSort(A[], n)
1. for i = 0 to n-1
2.     for j = 0 to n-i-1
3.         if A[j] > A[j+1]
4.             swap A[j] and A[j+1]

📋 Properties of Bubble Sort

PropertyValue
Best Time Complexity    O(n) (when already sorted)
Average/Worst Time Complexity    O(n²)
Space Complexity    O(1) (in-place)
Stability    Yes (it preserves order of equal elements)
Type        In-place, Stable


C Program Bubble Sort


#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        // Last i elements are already in place
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i=0; i<n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void readArray(int arr[], int n) {
    for (int i=0; i<n; i++)
        scanf("%d", &arr[i]);
    
}
int main() {
    int arr[50] ;
    int n;
    
    printf("Enter the number of elements \n");
    scanf("%d",&n);
    printf("Enter the array elements\n");
    readArray(arr,n);
    
    printf("Original array: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Output
Enter the number of elements 
5
Enter the array elements
3 2 7 6 5
Original array: 3 2 7 6 5 
Sorted array: 2 3 5 6 7 

The basic Bubble Sort always completes all passes even if the array is already sorted early.

✅ Optimized Bubble Sort checks if any swapping happened during a pass:

  • If no swap occurs in a full pass, the array is already sorted.

  • Then we can stop early and save time!

Modified Algorithm (Optimized Bubble Sort)

Optimized Bubble Sort Algorithm:

  1. Start from the first element.

  2. Initialize a flag swapped to false.

  3. Compare adjacent elements:

    • If the current element is greater than the next, swap them and set swapped = true.

  4. After each inner loop pass:

    • If swapped == false, break (array is sorted).

  5. Otherwise, repeat for the unsorted part.

✍️ Optimized Pseudocode

OptimizedBubbleSort(A[], n)
1. for i = 0 to n-1 
2. swapped = false 
3. for j = 0 to n-i-1 
4. if A[j] > A[j+1] 
5. swap A[j] and A[j+1] 
6. swapped = true 
7. if swapped == false 
8. break

C Program - Optimized Bubble Sort
#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    int swapped;
    for (i = 0; i < n-1; i++) {
        swapped = 0; // Initially no swap
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1; // Swap happened
            }
        }
        // If no two elements were swapped, break
        if (swapped == 0)
            break;
    }
}

void printArray(int arr[], int n) {
    for (int i=0; i<n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void readArray(int arr[], int n) {
    for (int i=0; i<n; i++)
        scanf("%d", &arr[i]);
    
}
int main() {
    int arr[50] ;
    int n;
    
    printf("Enter the number of elements \n");
    scanf("%d",&n);
    printf("Enter the array elements\n");
    readArray(arr,n);
    
    printf("Original array: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

📋 Properties of Bubble Sort

    
PropertyValue
    Best Time Complexity    O(n) (when already sorted)
    Average/Worst Time Complexity    O(n²)
    Space Complexity    O(1) (in-place)
    Stability    Yes (it preserves order of equal elements)
    Type    In-place, Stable

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more