Bubble Sort Algorithm | Board Infinity

Introduction

In this article, we will learn about the bubble sort algorithm and its implementation with the help of examples. When two neighboring elements are compared and swapped until they are in the desired order, the sorting technique known as bubble sort is used. In each iteration, each element of the array moves to the end, much to the movement of air bubbles in the water that rise to the surface. So, a bubble sort is what it is called.

The most straightforward sorting method is Bubble Sort, which repeatedly switches nearby components if they are in the wrong order. Large data sets should not be used with this approach due to its high average and worst-case time complexity. Bubble sort takes minimum time (Order of n) when elements are already sorted. Hence it is best to check if the array is already sorted or not beforehand, to avoid O(N2) time complexity.

How does Bubble Sort Work?

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

First Pass:

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

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, the 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), the algorithm does not swap them.

Second Pass:

Now, during the 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 )

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 )

Illustration:

To solve the problem, follow these steps:

Use two variables, I and j, in a nested for loop to iterate through the input array so that 0 I n-1 and 0 j n-i-1
If these neighboring components may be swapped and arr[j] is greater than arr[j+1], otherwise, go on.
Print the sorted array.

Bubble Sort Code

// C program for implementation of Bubble sort
#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;
}

write your code here: Coding Playground

Output:

Sorted array:
1 2 4 5 8

Time Complexity: O(N2)

Auxiliary Space: O(1)

Conclusion

Bubble sort is frequently used to illustrate the idea of a sorting algorithm because of how straightforward it is. It is well-known in computer graphics for its ability to find a little fault (such as a swap of just two elements) and correct it with only linear complexity (2n). Bubble sort performs the swapping of adjacent pairs without the use of any major data structure. Hence Bubble sort algorithm is an in-place algorithm.