**Bubble sort **is the simplest sorting technique among all the sorting techniques known to us. It is a simple sorting technique as it is very easy to understand, easy to implement, and also very easy to analyze. It is a comparison based sorting technique. The complexity of this sorting technique is very high and the complexity totally depends on the number of elements. In this sorting technique the pairs of the elements are compared from the beginning of the array and continue up to the last element for the first pass and after the first pass, the largest or the smallest element reaches the last according to the ascending or descending order of sorting respectively. In the second pass again the pairs of elements will be compared but it will continue up to the second last element of the array and so on.

**PROCEDURE OF BUBBLE SORT WITH EXAMPLE:**

Suppose there are 5 unsorted elements in array as following:

Now if the elements are sorted using the bubble sort technique, the number of passes required will be **(5 - 1) = ****4** i.e. if the number of elements of the array is **n** then n - 1 passes are required to sort the elements using the bubble sort technique.

For sorting the above-mentioned array in ascending order the **following passes **have to be followed:

__Pass-1__

The pairs of the elements will be compared and the largest element will be reached to the last of the array and the steps will be:

First, the **first pair of elements** will be compared and as **98 ****is greater than ****12 **it will **be swapped**.

The array will be:

Now the next pair will be compared and again **it will be swapped** as **98**** is also greater than ****45**. The array now will be:

Similarly, **98 ****and ****34**** will be compared** and will be **swapped and the array** will be:

Now for the first pass, the **last pair of elements will be compared**. In this case, **98**** is greater than ****21**.

So, it will be swapped and at the end of the first pass the biggest element of the array i.e. 98 will be positioned at the last i.e. it's the final sorted position. After pass 1 the array will be:

In this pass, the total number of comparisons is: **5 - 1 = ****4**

__Pass 2:__

The last element of the array has already reached its sorted position so in **the ****2nd pass** the last element will not be taken in the pair of elements again.

At the beginning the array elements are:

The first pair of elements will be compared again and **will not be swapped**** ****as ****12**** is lesser than ****45**. So the array will remain the same.

The next **pair of elements is ****45**** and ****34****,** after comparing these two elements **will be swapped** and the array will be:

For the 2nd pass, the **last pair is ****45**** and ****21** which **will be swapped** as **45**** is greater than ****21**. The final array after 2nd pass:

After this pass, the last **two elements ****45 ****and ****98** reached their sorted position. In this pass, the number of comparisons is **5 - 2 = ****3**

__Pass 3:__

At the beginning of the **3rd pass** the array elements are:

Here **45**** and ****98** are already positioned in their **sorted position**. Again the first pair of elements will be compared. There **will be no swapping** as **12**** is lesser than ****34**. So the array elements will remain the same.

The second pair of this pass is **34**** and ****21**, after comparison, the elements **will be swapped as ****34**** is greater than ****21**. So the array after this pass is:

After this pass logically the last three elements should be sorted already. Only one pair i.e. the first pair would remain unsorted. But in this case, it can be seen that after this pass all the elements of the array are already sorted.

The **total number of comparisons in this pass** is **5 - 3 = ****2**

Though the elements are sorted already after this pass according to the logic of bubble sort the fourth pass will also be there.

__Pass 4:__

At the starting of this pass the array is:

Here only the **first pair will be compared** and as **12**** is already lesser than ****21** it **will not be swapped**** **and the array will remain the same.

This is the final pass and the **total number of comparisons of this pass** is: **5 - 4 = ****1**

After this pass the final sorted array will be:

```
INPUT: An unsorted array a[6,2,4,1,…………….,n]
OUTPUT: An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)
PROCESS:
Step 1: [Taking the number of elements from the user]
Read n
Step 2: [Take the unsorted elements from the user in an array]
For i=0 to n
Read arr[i]
Step 3: [Print the unsorted array]
For i=0 to n
Print arr[i]
Step 4:[Sorting the unsorted elements]
For i=0 to i<n repeat
For j=0 to j<n-i-1
If(a[j]>a[j+1]) then
Set t <- a[j]
Set a[j] <- a[j+1]
Set a[j+1] <- t
[End of ‘If’]
[End of inner ‘For’ loop]
[End of outer ‘For’ loop]
Step 5: [Printing the sorted array]
For i=0 to n
Print arr[i]
Step 6: Stop.
```

__CHARACTERISTICS:__

**1.** It is a comparison-based sorting technique.

**2.** It is an in-place sorting algorithm as it does not require any extra space for sorting.

**3.** The best-case complexity of the bubble sort algorithm is **O(n)**

**4.** The sorting is done by swapping the adjacent elements if they are not incorrect order

**5.** It is a stable sorting algorithm

__APPLICATIONS:__

**1.** Bubble sort is used in a polygon filling algorithm in graphics to sort the x coordinates of a particular scan line.

**2.** The concept of sorting can be understood by the learners easily by learning the bubble sort algorithm.

__ADVANTAGES:__

**1.** The algorithm is very easy to understand, implement, and analyze.

**2.** The coding of this algorithm is not lengthy, hence it is very simple.

**3.** It does not require extra spaces for sorting.

**4.** It performs well on a sorted array.

__DISADVANTAGES:__

__TIME COMPLEXITY:__

For this above algorithm the **best case****, ****average case**,** and the **worst-case** **time complexity of bubble sort will be the **same****.**

For **n**** number of elements,** the number of comparisons in the **first pass is** **n - 1**, in the second pass **n - 2,** and so on, and in **the last pass the number of comparisons is ****1** as explained earlier through example.

Therefore for **n** number of elements, the **total number of comparisons to sort** the array is:

If the algorithm can be changed such that if there is no swapping in a pass then the algorithm will stop working and will come out from the outer for loop. In that case, the best case (when the array is already sorted) there will be no swapping in the first pass and so the **outer for loop** will run only for **ones**.

__SPACE COMPLEXITY:__

The **space complexity of this algorithm** is **O(1)** as it is an **in-place algorithm **and it does not require any extra space for performing the sorting.

Related

- Selection Sort
- Insertion Sort
- Quick Sort using recursion
- Quicksort Iterative
- Merge Sort using recursion
- Merge Sort Iterative
- 3 way Merge Sort
- Heap Sort using recursion
- Heap Sort Iterative
- Radix Sort for positive integer
- Bucket Sort
- Counting Sort
- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort