Link copied to clipboard. Share away!

Dismiss

Published on 07 Mar 2020

**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.

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).

```
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
```

```
void bubble_sort(int arr[], int n)
{
int i, j, temp;
//the first for loop n elements and n-1 passesfor(i = 0; i < n; i++)
{
// comparisons done at each passfor(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;
}
}
}
}
```

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.

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

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

```
#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;
}
}
// If no two elements were swapped by inner loop, then break
if (flag == 0)
break;
}
for (i=0; i < n; i++)
cout<<arr[i]<<" ";
}
```

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×