Bubble Sort

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. Here’s how the Bubble Sort algorithm works:

Algorithm:

1. Start from the beginning of the array.
2. Compare each pair of adjacent elements.
3. If the elements are in the wrong order (e.g., the current element is greater than the next one), swap them.
4. Continue this process until the end of the array is reached.
5. Repeat the above steps for each element in the array until the entire array is sorted.

Here’s the Bubble Sort algorithm implemented in C:

#include <stdio.h>

// Function to perform Bubble Sort
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        // Last i elements are already in place, so no need to check them
        for (j = 0; j < n - i - 1; j++) {
            // Traverse the array from 0 to n-i-1
            // Swap if the element found is greater than the next element
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Output:

Original array: 
64 34 25 12 22 11 90 
Sorted array: 
11 12 22 25 34 64 90 

Code Explanation :

1. bubbleSort Function

void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        // Last i elements are already in place, so no need to check them
        for (j = 0; j < n - i - 1; j++) {
            // Traverse the array from 0 to n-i-1
            // Swap if the element found is greater than the next element
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

• Purpose: Sorts the array in ascending order using the Bubble Sort algorithm.
• How it works:
  • The outer loop (i) runs n-1 times, where n is the size of the array. Each iteration places the largest unsorted element in its correct position.
  • The inner loop (j) compares adjacent elements and swaps them if they are in the wrong order (i.e., arr[j] > arr[j + 1]).
  • After each iteration of the outer loop, the largest unsorted element “bubbles up” to its correct position at the end of the array.

2. printArray Function

void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

• Purpose: Prints the elements of the array.
• How it works:
  • Iterates through the array and prints each element followed by a space.
  • After printing all elements, it adds a newline (\n) for better readability.

3. main Function

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

• Purpose: Drives the program.
• How it works:
  1. Declares and initializes an array arr with unsorted integers.
  2. Calculates the size of the array (n) using sizeof(arr) / sizeof(arr[0]).
  3. Prints the original array using the printArray function.
  4. Calls the bubbleSort function to sort the array.
  5. Prints the sorted array using the printArray function.

Key Points

1. Bubble Sort:
   • Time Complexity: O(n²) in the worst and average cases.
   • Space Complexity: O(1) (in-place sorting).
   • It is a simple but inefficient sorting algorithm for large datasets.
2. Array Size Calculation:
   • sizeof(arr) gives the total size of the array in bytes.
   • sizeof(arr[0]) gives the size of one element in bytes.
   • Dividing them gives the number of elements in the array.
3. Swapping:
   • A temporary variable (temp) is used to swap two elements.