Bubble Sort is a simple sorting algorithm that works by
repeatedly comparing and swapping adjacent elements in an array until they are
in the correct order. It is called bubble sort because the smaller elements
"bubble" to the top of the array, while the larger elements sink to
the bottom.
How Bubble Sort Works
Bubble sort works by iterating through the array from left to right and comparing each pair of adjacent elements. If the element on the left is larger than the element on the right, they are swapped. This way, the largest element in the array moves to the rightmost position in each iteration. This process is repeated until no more swaps are needed, which means the array is sorted.
To illustrate how bubble sort works, let's use the example of sorting the array [30,90,50,10,40] in ascending order.
First Iteration/Pass:
The first step is to compare the first two elements, 30 and 90. Since 30 is smaller than 90, they are already in order and no swap is needed. The array remains [30,90,50,10,40].
The second step is to compare the second and third elements, 90 and 50. Since 90 is larger than 50, they are out of order and need to be swapped. The array becomes [30,50,90,10,40].
The third step is to compare the third and fourth elements, 90 and 10. Since 90 is larger than 10, they are out of order and need to be swapped. The array becomes [30,50,10,90,40].
The fourth step is to compare the fourth and fifth elements, 90 and 40. Since 90 is larger than 40, they are out of order and need to be swapped. The array becomes [30,50,10,40,90].
At this point, we have completed one pass through the array. Notice that the largest element, 90, has moved to the last position. This is a property of bubble sort: after each pass, the largest element in the unsorted part of the array moves to the end.
Second Iteration/Pass:
We repeat the same process for the remaining four elements in the array: [30,50,10,40]. We compare 30 and 50 and find them in order. We compare 50 and 10 and swap them. We compare 50 and 40 and find them in order. The array becomes [30,10,40,50,90].
Third Iteration/Pass:
We repeat the same process for the remaining three elements in the array: [30,10,40]. We compare 30 and 10 and swap them. We compare 30 and 40 and find them in order. The array becomes [10,30,50,40,90].
Fourth Iteration/Pass:
We repeat the same process for the remaining two elements in the array: [10,30]. We compare 10 and 30 and find them in order. The array becomes [10,30,50,40,90].
At this point, we have completed four passes through the array and no more swaps are needed. The array is sorted in ascending order.
Code Snippet:
Java:
int a[]={30,10,40,80,60,20};
int l=a.length;
boolean flag=false;
for(int i=0;i<l-1;i++)
{flag=false;
for(int j=0;j<l-i-1;j++)
{
if(a[j]>a[j+1])
{
//swapping them
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=true;
}
}
if(flag==false)
break;
}
Python:
a=[30,10,40,80,60,20]
l=len(a)
for i in range(0,l-1):
flag=false
for j in range(0,l-1-i):
#swapping
if a[j]>a[j+1]:
temp=a[j+1]
a[j+1]=a[j]
a[j]=temp
flag=true
if flag==false:
break
print (a)
Conclusion:
Bubble sort has a time complexity of O(n^2), where n is the number of elements in the array. This means that it takes n^2 comparisons to sort an array of n elements. Bubble sort is not very efficient for large arrays because it performs many unnecessary comparisons.
Bubble sort is a stable sorting algorithm, which means that it preserves the relative order of equal elements in the array. For example, if we have an array of names with their ages as [Alice-20, Bob-20, Claire-21, Dave-19], bubble sort will not change the order of Alice and Bob because they have the same age.
Related Video:
Bubble sort is also an in-place sorting algorithm, which
means that it does not use any extra space to sort the array. It only modifies
the original array by swapping elements.