Bubble Sort Algorithm: In this article, we will learn more about the Bubble sort algorithm. Bubble sort is a simple searching algorithm that repeatedly swaps adjacent elements to arrange them in sorted order, either in decreasing or increasing order. It is suitable for small or medium data sets. The average and worst-case complexity of the bubble sort algorithm is O(n2), where n is the number of items in the list.
Let us learn the code for the C program for selection sort. You can start your career with PW Skills Complete Decode Full Stack Web Dev 1.0 to boost your career and give you a strong foundation. The complete course offers recorded and live lectures and any-time doubt-solving.
What is the Bubble Sort Algorithm?
Bubble Sort is a linear sorting algorithm used to sort data items by repeatedly swapping the items until they are not in the sorted order. It is known as bubble sorting because the sorting takes place just like moving bubbles in water. Similarly, as the bubbles rise to the surface at the end, the bubble element moves to the end in each iteration.
Bubble Sort Algorithm
Let us consider an array ‘arr’ consisting of n elements inside. We will use the bubble sort algorithm to swap the values one by one until they get sorted.
| Bubble Sort Algorithm |
| 1. bubbleSort(arr)
2. for all elements in the array 3. If arr[i] > arr[i+1] 4. Swap (arr[i], arr[i+1]) 5. end if 6. end for 7. return arr 8. end bubbleSort |
Working of Bubble Sort Algorithm
Let us understand bubble sort by using an example. Consider an array consisting of five elements in an unorganized order. arr = { 16, 7, 25, 9, 2}, we will now use the bubble sort algorithm to sort the array element.
1. First Pass
In the first pass, the algorithm will select the first two elements using the swap function. It will compare them and if element at arr[i-1] is greater than element at arr[i], then swap both the element.
Now, after swapping, we will move on to the next element. But at the next element at arr[i-1] is not greater than element at arr[i], then we do not swap both the elements and move to the next element.
Now, we can see the element at arr[2] is greater than element at arr[3], hence we will swap.
Now, we will compare the last two elements. The elements at arr[3] are greater than arr[4]. Hence, we swap again.
Now, after the first pass, the elements arranged are given below.
2. Second Pass
Now, we will start again in the second pass from the element at arr[0] and element at arr[1]. Now, we see the element at 0th index is smaller than element at the first index, hence we do not swap.
Now, we check that at arr[1] the element is greater than element at arr[2], hence we swap the element.
Now, we again swap the elements at arr[2] and arr[3] indexes.
Now, we check the element at arr[3] is not greater than element at arr[4]. Hence, we will not swap the element. Hence, the elements after the second pass will look like this.
3. Third Pass
Now, at the third pass the elements in the array looks like this.
Elements at arr[0] are smaller than elements at arr[1], hence we will not swap the elements. Now, we will swap the elements at the next two positions.
Now, after the element at arr[2] we can see the elements are in correct order. Hence, the element order after the third pass will look like this.
4. Fourth Pass
Now, our array elements look like this in the fourth pass. We can see the elements at arr[0] index is greater than element at arr[1], hence we will swap both of them.
Now, our array is sorted, all the elements are its correct position. It takes (N-1) pass to completely sort the elements of array.
| 2 | 7 | 9 | 16 | 25 |
Advantages of Bubble Sort Algorithm
The Bubble sort algorithm is one of the sorting algorithms used to sort the array items in either ascending or descending order.
- It is simple algorithm easy to understand and implement.
- It is beginner friendly algorithm and can be good for explanatory purposes.
- The space complexity for bubble sort algorithm is constant, O(1). No additional data or memory is required, it is an inplace sorting algorithm.
- It can be adapted easily.
- It is a stable algorithm, which means that it preserves the relative order of equal elements found in the array.
Disadvantages of Bubble Sort Algorithm
Despite being a simple and easy to implement sorting algorithm, bubble sort has some disadvantages, as given below.
- The time complexity of the bubble sort algorithm is quadratic, O(n2), where N is the size of array.
- It is not suitable for large datasets. As the element in array increases the performance of bubble sort decreases quardatically.
- It is very less used in the practical world.
Complexity Analysis of Bubble Sort Algorithm
The complexity analysis of bubble sort is given in the table below.
| Bubble Sort Complexity Analysis | |
| Complexity Type | Selection Sort |
| Time Complexity | O(n^2) |
| Space Complexity | O(1) |
Bubble Sort Algorithm FAQs
What is Bubble Sort algorithm?
Bubble Sort is a linear sorting algorithm used to sort data items by repeatedly swapping the items until they are not in the sorted order.
What is the time complexity of the Bubble sort algorithm?
The time complexity of the bubble sort algorithm is quadratic which is O(n^2).
How many passes does it take to complete the sorting using bubble sort?
It takes N-1 passes to sorting using bubble sort algorithm. The N here is the size of the element.
Is bubble sort a stable algorithm?
Yes, bubble sort is a stable algorithm. It preserves the relative order of elements equal in the array.
Is bubble sort suitable for large datasets?
No, bubble sort is suitable for smaller datasets only. However, it is not generally used in the real world.
