**Bubble sort** begins by comparing the first two adjacent elements of an array, and if the first element is greater than second, then the two elements must be swapped else need not swap the element. Again second and third elements are compared and swapped if it is necessary and this process goes on until last and second last element is compared and swapped. This is the first step of Bubble sort. If there are n elements to be sorted then, the process mentioned above should be repeated n-1 times to sort the elements.

**Bubble Sort Algorithm**

Let’s take an unsorted array of n elements as an example: 6 2 4 9 1 3

**Step 1: (First pass)**

In the first pass, there were n elements and n-1 comparisons (i.e., 6 elements and 5 comparisons). And the largest value 9 is now in place.

**Note:** So for the next pass, the last element 9 need not be compared (since already placed in the right position).

**Step 2: (Second Pass)**

The last element 6 need not be compared with the 9, since 9 is already placed in the right order. At the end of the second pass, the second **largest value 6 is now in place.**

**Step 3: (Third Pass)**

At the end of the third pass, the third largest value 4 is now in place.

**Step 4: (Fourth Pass)**

**Note: 4 6 9 have already been placed in the right position (So, no need of comparing those elements)**

Here, when you take a look at the order of elements in the last step it is found that the elements are sorted, but our algorithm does not know if it is completed. This technique needs one more step without any swap to know it is sorted.

**Step 5: (Fifth Pass)**

In this step 5, no swapping of elements throughout the whole pass, hence the sorting technique is stopped and the array elements were sorted in an ascending order.

** Note: **Since each pass places the next largest value in place, the total number of passes necessary will be (n−1). After completing the (n−1) passes, the smallest item must be in the correct position with no further processing required. Here there were 6 elements, so 5 passes (n-1).

**Algorithm for Bubble Sort**

start Bubble_Sort(array)

for all elements of array

if array[i] > array[i+1]

swap(array[i], array[i+1])

end if

end for

return array

end Bubble_Sort

**Implementation of Bubble sort**** (Using C)**

void bubble_sort(int arr[], int n)

{

int i, j, temp;

//the first for loop n elements and n-1 passes

for(i = 0; i < n; i++)

{

// comparisons done at each pass

for(j = 0; j < n-i-1; j++)

{

if( arr[j] > arr[j+1])

{

// swap the elements

temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

}

**Complexity Analysis of Bubble Sort**

**Time Complexity of Bubble Sort**

In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in the 3rd pass and so on. So the total number of comparisons will be,

(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1

Sum = n(n-1)/2 = ½ [ n^{2} – n]

i.e O(n^{2})

Hence the time complexity of Bubble Sort is O(n^{2}).

Worst case time complexity: O(n^{2})

Average case time complexity: O(n^{2})

Best case time complexity: O(n) (i.e., when the list is already sorted.

**Space Complexity of Bubble Sort**

The space complexity for Bubble Sort is O(1) because only a single additional memory space is required i.e. for temp variable.

**Advantages of Bubble sorting**

- One of the simplest sorting techniques
- Space complexity is O(1)

**Bubble sort Implementation in ****C++**

#include <iostream>

using namespace std;

void bubble_sort(int arr[], int n);

int main()

{

int arr[50], n, i;

cout<<"Enter the number of elements: ";

cin>>n;

cout<<"\nEnter the elements: \n";

for(i=0; i<n; i++)

cin>>arr[i];

bubble_sort(arr, n);

return 0;

}

//Bubble sort algorithm

void bubble_sort(int arr[], int n)

{

int i, j, temp;

bool flag;

for (i = 0; i < n-1; i++)

{

flag = 0;

for (j = 0; j < n-i-1; j++)

{

if (arr[j] > arr[j+1])

{

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

flag = 1;

}

}

// Ifno two elements were swapped by inner loop, then break

if (flag == 0)

break;

}

for (i=0; i < n; i++)

cout<<arr[i]<<" ";

}