Illustration of Bubble Sorting in one Dimensional Array

Introduction

Bubble sorting is one of the common methods of sorting an array. In this type of sorting operation, two elements of an array are compared at a time, and depending upon the arrangement required (ascending or descending), the values are interchanged. In this type of sorting, repeated trips are made to the array, and the smallest / greatest element bubbles up to the top, hence the name bubble sorting.

Illustration of Bubble Sorting

Consider the following array of four items.

Now we will sort this array in ascending order using bubble sort.

From the above illustration, we see that for an array of four elements, we need to process the array three times (as indicated by the three iterations) to get the sorted array. In the above illustration, for the first iteration in the first pass, the first element of the array 90 is compared with the second element 45. Since 90 is greater than 45, the two values are interchanged. For the second pass, 90 is compared with 70, and the values are interchanged. In the third pass, 90 is compared with 15, and values interchanges.

By doing iteration, the largest number moves to the last element of the array.

In the second iteration, in the first pass, since 45 is less than 70, no exchange of value is done. In the second pass, 70 is compared with 15, and the values get interchanged. After this iteration, the second largest number goes to the second last element of the array.

In the third iteration, we only have one pass, where 45 is compared with 15, and the values are interchanged. After this iteration is complete, the array is available in the sorted order.

As seen from the above illustration, for an array of four elements, we need three iterations.

This is a general rule with the bubble sort technique, where for an array of n elements, n-1 iterations are required to be made to the array to accomplish sorting.

Consider a program for sorting an array in ascending order using bubble sorting.

#include<stdio.h>
#include<conio.h>
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void 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 in ascending order: \n");
    printArray(arr, n);
    getch();
}

Output

Summary

Bubble Sort is a simple sorting algorithm used to arrange elements in an array in ascending order by repeatedly comparing and swapping adjacent elements that are in the wrong order. The algorithm consists of two main components: the bubble Sort function, which implements the sorting logic using nested loops to traverse the array multiple times, and the print Array function, which is a helper function that prints the array's elements.

In the C program, the main function initializes the array, calls bubble Sort to sort it, and prints both the original and the sorted array. However, Bubble Sort is easy to understand and implement. It is primarily used for educational purposes or when sorting small datasets.