# Bubble Sort Algorithm - GATE CSE Notes

Bubble sort is a popular sorting algorithm that we prefer to sort the components of an array in a clear and particular order. Essentially, in this algorithm, we need to compare the two adjacent elements and perform a swap operation on them until they do not come in the planned order.

If the positions of the components are right, then we have to move to the next iteration; else, we need to perform a swap strategy.

## Bubble Sort Algorithm

Let’s assume that arr is an array with n members (elements):

1. begin BubbleSort(arr)
2. for all array elements
3. if arr[i] > arr[i+1]
4. swap(arr[i], arr[i+1])
5. end if
6. end for
7. return arr
8. end BubbleSort

## Working of Bubble Sort Algorithm

Let’s now examine how bubble sort algorithms function.

We are using an unsorted array to better understand how the bubble sort algorithm operates.

Let the array’s components be:

### First Pass:

Starting with the first two components, we’ll sort. To determine which component is greater, we shall compare them.

In this case, 31 is greater than 12 (31 > 12), hence nothing needs to be done because these components are already sorted. It’s time to compare 31 to 25 at this point.

25 is less than 31 here. This calls for a swap operation to be made. The new array will be obtained after the swap:

Now, we will compare 31 and 34.

34 is higher than 31 in this case. Since these components are already sorted, there is no need for swap operations in this situation.

Now, we will compare the two elements 34 and 9.

In this case, 9 is less than 34. None of these components are sorted. Therefore, we must do a swap operation. We have now reached the end of the array. As a result, here is how the array appears following the first pass:

Now, we have to think about the second iteration.

### Second Pass

We’ll proceed in the same way as we did during the first pass likewise here.

9 is less than 31 here. As a result, we must exchange here. The new array appears as follows:

We are moving to the third iteration now.

### Third Pass

We will proceed in the same manner that we did in the first and second passes likewise here.

9 is less than 25 here. We must do a swap operation, and the outcome is as follows:

Now, we are moving to the fourth iteration.

### Fourth pass

So, after the fourth iteration, this is how the array will look.

As a result, there is no swap procedure required in this situation. Now that the array is sorted.

## Bubble Sort Complexity

One of the most trustworthy sorting algorithms is bubble sort. Here, we’ll talk about the three time complexity case studies. Best, typical, and worst case scenarios.

### 1. Time Complexity

Case Time Complexity
Best Case O(n)
Average Case O(n2)
Worst Case O(n2)

### 2. Space Complexity

Space Complexity O(1)

### Program: Write a program to implement bubble sort in C language.

#include<stdio.h>

void print(int p[], int q) //function to print array elements

{

int r;

for(r = 0; r <q; r++)

{

printf(“%d “,p[r]);

}

}

void bubble(int p[], int q) // function to execute bubble sort

{

int r, s, temp;

for(r = 0; r < q; r++)

{

for(s= r+1; s < q; s++)

{

if(a[s] < a[r])

{

temp = a[r];

a[r] = a[s];

a[s] = temp;

}

}

}

}

void main ()

{

int r, s,temp;

int a[5] = { 9, 34, 31, 11, 25};

int p = sizeof(a)/sizeof(a[0]);

printf(“Before organizing array components are – \n”);

print(p, q);

bubble(p, q);

printf(“\nAfter sorting array elements are – \n”);

print(p, q);

}

Output

Before sorting array elements are-

9,34,32,12,26

After sorting array elements are –

9, 12, 25,31,34

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility CriteriaGATE 2023GATE Admit CardGATE Syllabus for CSE (Computer Science Engineering)GATE CSE NotesGATE CSE Question Paper, and more.

Also Explore,