## Bubble Sort in Data Structure

In the next section of the tutorial, we will discuss the Bubble Sort in Data Structure which sorts an unsorted list by comparing each item in the list with the item next to it, and swapping them if required.

Now, let’s move further to the introduction of Bubble Sort in Data Structure.

## What is Bubble Sort in Data Structure?

Bubble Sort is the most commonly used sorting method in data structure. It lies in the category of exchange sorts, which is the most efficient general-purpose sort. It follows simple rules for sorting list of elements.

• In Bubble Sort, elements are exchanged that are unordered.
• This exchange of elements continues until the whole list of elements are sorted.
• The list of elements is divided into two subgroups, i.e. sorted and unsorted lists.
• Each time the smallest element in the unordered subgroup is bubbled. and then it is moved to the sorted list.
• Then the next smallest element is targeted in the unsorted list and then it is bubbled and moved to the sorted list.
• This process continues until all the elements are sorted.

Now, we will dive deep into the concept used in Bubble Sort in Data Structure.

## Concept used in Bubble Sort

As we know, in Bubble Sort, the list is divided into two subgroups, i.e. sorted list and unsorted list, the selection and exchange of the smallest element in the unsorted list is carried out until the whole list of elements is sorted. This process follows a set of rules and concepts that is discussed below.

• The list of element is divided into two parts on the basis of sorted and unsorted elements.
• The smallest element from the unsorted list is selected and bubbled.
• Then the smallest element is moved to the sorted list.
• This is first pass, it gradually increases the sorted list and decreases the unsorted list.
• With sorting of each element, the wall moves one element to the right to carry out the bubbling on the next smallest element in the unsorted list.
• One sort pass is completed each time an element is moved from the unsorted list to the sorted list.
• So for n number of elements in the list, n-1 sort passes are carried out by the Bubble Sort to sort the complete element list.

Now that we have understood the concept used in Bubble Sort. We shall move further to the Bubble Sort Algorithm.

## Bubble Sort Algorithm

Now, we will write the Algorithm of Bubble Sort before we implement it in a programming language to perform operations.

```Algorithm BubbleSort (ElementList, last)
1 set current to 0
2 set sorted to false
3 loop (current <= last AND sorted false)
1 set walker to last
2 set sorted to true
3 loop (walker > current)
1 if (walker data < walker - 1 data)
1 set sorted to false
2 exchange (ElementList, walker, walker - 1)
2 end if
3 decrement walker
4 end loop
5 increment current
4 end loop
end BubbleSort```
• Here, array of elements are sorted using this algorithm.
• Each element is compared and exchanged with the sorted list until the list is completely sorted.
• list must contain at least one element.
• last contains the index values of the last element in the list.
• If any exchange is carried out between the unsorted and sorted list, means the list is not completely sorted.
• After the comparison and exchange of elements between the sublist is completed. The list is sorted in ascending order.
• Each iteration specifies one sort pass. While there are n-1 total sort passes for n number elements.

## Working of Bubble Sort

The working of Bubble Sort is quite simple, similar to the other sorting methods which we will discuss in the later sections of the tutorial. Let’s understand the working of Bubble Sort with the help of the points given below.

• Here, the elements are sort passed in each iteration, where the smallest element is bubbled in the unsorted sublist of the array.
• Adjacent elements are compared and if found to be unordered are exchanged, gradually ordering the elements.
• The smallest element is initially bubbled up in the unordered part of the array. Then the sort continues with more sort pass for each element in the unsorted list.
• This whole process continues and ends up sorting the array elements in a particular order.

We will look into an example given in the below diagram to understand the working of the Bubble Sort.

• Here, the original list of elements is unsorted.
• In sort pass 1, 32 is selected and compared with 56, it is found to be less than 56, both are exchanged with each other and step down one element.
• Then 32 is compared with 8, it is found to be greater than 8, so no exchange takes place. Again bubble steps down one element.
• Then 45 is compared with 8, it is found to be out of sequence, so both are exchanged with each other and step down one element.
• Now, 8 is compared with 78, and both are exchanged.
• Lastly, 8 is compared with 23, and both are exchanged.
• Eventually, 8 is compared with all the elements are it is placed in the first position and the wall moved up one position.
• This whole process of comparison and exchange for each element takes place continuously until the list of elements is sorted completely.

Now that we are familiar with the working of the Bubble Sort, we will analyze the time and space complexity of the Bubble Sort Algorithm.

## Time and Space Complexity of Algorithm

##### Worst Case

Time Complexity

O(n) O(n^2) O(n^2)
Space Complexity O(1)

## Bubble Sort Implementation

Now that we understand the concept of Bubble Sort and also we have written the algorithm of Bubble Sort, now we can implement Bubble Sort in a programming language to perform the operation. Here, we will implement Bubble Sort in C and C++

#### Implementation in C

Code:

```#include<stdio.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void bubble_sort(int nums[], int size)
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - i - 1; j++)
{
if (nums[j] > nums[j + 1])
{
swap(&nums[j],&nums[j+1]);
}
}
}
}

int main()
{
int arr[] = {9,8,7,6,5,4,3,2,1};
int n = sizeof(arr)/sizeof(arr[0]);
bubble_sort(arr,n);
printf("Sorted Array \n");
for(int i = 0; i < n; i++)
{
printf("%d ",arr[i]);
}
return 0 ;
}```

Output:

```Sorted Array
1 2 3 4 5 6 7 8 9```

#### Implementation in C++

Code:

```#include<bits/stdc++.h>
using namespace std;

void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void bubble_sort(int nums[], int size)
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - i - 1; j++)
{
if (nums[j] > nums[j + 1])
{
swap(&nums[j],&nums[j+1]);
}
}
}
}

int main()
{
int arr[] = {9,8,7,6,5,4,3,2,1};
int n = sizeof(arr)/sizeof(arr[0]);
bubble_sort(arr,n);
cout<<"Sorted Array \n";
for(int i = 0; i < n; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}```

Output:

```Sorted Array
1 2 3 4 5 6 7 8 9```

In the next section of the tutorial, we will discuss the Insertion Sort in Data Structure and its concept and the algorithm of bubble sort for performing different sorting operations in detail.