A Quick Guide to Bubble Sort Algorithm

Introduction

In this article, we will learn about the bubble sort algorithm and its implementation with the help of examples. When two neighboring elements are compared and swapped until they are in the desired order, the sorting technique known as bubble sort is used. In each iteration, each element of the array moves to the end, much to the movement of air bubbles in the water that rise to the surface. So, a bubble sort is what it is called.

The most straightforward sorting method is Bubble Sort, which repeatedly switches nearby components if they are in the wrong order. Large data sets should not be used with this approach due to its high average and worst-case time complexity. Bubble sort takes minimum time (Order of n) when elements are already sorted. Hence it is best to check if the array is already sorted or not beforehand, to avoid O(N2) time complexity.

How does Bubble Sort Work?

Input: arr[] = {5, 1, 4, 2, 8}

First Pass:

• Bubble sort starts with the very first two elements, comparing them to check which one is greater.

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, the algorithm compares the first two elements and swaps since 5 > 1.

( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), the algorithm does not swap them.

Second Pass:

• Now, during the second iteration it should look like this:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )

Third Pass:

• Now, the array is already sorted, but our algorithm does not know if it is completed.

The algorithm needs one whole pass without any swap to know it is sorted.

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Illustration:

To solve the problem, follow these steps:

• Use two variables, I and j, in a nested for loop to iterate through the input array so that 0 I n-1 and 0 j n-i-1
• If these neighboring components may be swapped and arr[j] is greater than arr[j+1], otherwise, go on.
• Print the sorted array.

Bubble Sort Code

Output:

Time Complexity: O(N2)

Auxiliary Space: O(1)

Conclusion

Bubble sort is frequently used to illustrate the idea of a sorting algorithm because of how straightforward it is. It is well-known in computer graphics for its ability to find a little fault (such as a swap of just two elements) and correct it with only linear complexity (2n). Bubble sort performs the swapping of adjacent pairs without the use of any major data structure. Hence Bubble sort algorithm is an in-place algorithm.