Explain Bubble Sort Algorithm?

Software Development
#1

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

How does Bubble Sort Work?

Input: arr[] = {5, 1, 4, 2, 8}

First Pass:

Bubble sort starts with very first two elements, comparing them to check which one is greater.

  • ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
  • ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
  • ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
  • ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

Now, during second iteration it should look like this:

  • ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
  • ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Third Pass:

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
  • ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Follow the below steps to solve the problem:

  • Run a nested for loop to traverse the input array using two variables i and j, such that 0 ≤ i < n-1 and 0 ≤ j < n-i-1
  • If arr[j] is greater than arr[j+1] then swap these adjacent elements, else move on
  • Print the sorted array

Below is the implementation of the above approach:

#include <stdio.h>
 
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
// A function to implement 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
        for (j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

/* 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]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Output:

Sorted array: 
1 2 4 5 8 

//Time Complexity: O(N2)
//Auxiliary Space: O(1)