Problem Statement: Given an array of N integers, write a program to implement the Bubble Sorting algorithm.

Examples:

Example 1:
Input: N = 5, array[] = {5,4,3,2,1}
Output: 1,2,3,4,5
Explanation: After sorting we get 1,2,3,4,5


Example 2:
Input: N = 6, array[] = {13,46,24,52,20,9}
Output: 9,13,20,24,46,52
Explanation: After sorting we get 9,13,20,24,46,52

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach: 

• Repeatedly swap 2 adjacent elements if arr[j] > arr[j+1] .
• Here, the maximum element of the unsorted array reaches the end of the unsorted array after each iteration.
• Unlike selection sort, here, sorting is done from the back as shown in the dry run.
•  After (N-1) iterations , we get a sorted array.

Dry Run:

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Code:

#include<stdio.h>

void bubble_sort(int arr[], int n) {
  // bubble sort
  int i,j;
  for ( i = 0; i < n - 1; i++) {
    for ( j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  printf("After Using bubble sort: \n");
  for (int i = 0; i < n; i++) {
    printf("%d ",arr[i]);
  }

}
int main() {
    int arr[] = {13,46,24,52,20,9};
    printf("Before Using Bubble Sort: \n");
    for(int i=0;i<6;i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
    int n = sizeof(arr) / sizeof(arr[0]);
    bubble_sort(arr, n);
    return 0;
}

Special thanks to Subhrajit Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article

Reference: https://takeuforward.org/data-structure/bubble-sort-algorithm/