Skip to main content

Bubble Sort | Java & Python | MyCodingNetwork | Alok Tripathi



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.

Quick Video Explanation:


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.

More To Explore:

Popular posts from this blog

YouTube Material 1| Hindi Video

Video Lecture- https://youtu.be/StCjnwfS0NQ Basic structure of a Java program public class xyz { public static void main(String args[]) { //Code //Code //Code //Code //Code }} public - access specifier/modifiers which makes the particular entity accessible throughout the program i.e., it can be accessed by other classes also. static - a keyword by which we don't have to create an object of that particular entity. void- return type keyword by which the function becomes non-returning type. main - name of the function String args[] - argument for main function Print Statement Syntax: System.out.println() ; Three types of Iteration statements are: for loop Example: for(int i=0; i<=5;i++) { //Code //Code //Code //Code //Code } The body of the above for loop will be executed 6 times. while loop( entry control loop) Syntax: while (condition) { //Code //Code //Code //Code //Code } The body of the above while loop will be executed continuously as long as the condition of the while is tr...

Pattern 1 | Java

Problem Statement: Write a program to draw the following pattern of NxN(where N is the input): * * * * * * * * * * * * * * * * * * * * * * * * * (here, N=5) THE CODE Output: Here, the input is 8 Simplification : In the above problem, two for loops are used: 1. The first for loop is having i as counter variable with  initial value of 1 and ending value of 10 with an updation statement i++. 2. The second for loop is having j as counter variable with initial value of 1 and ending value of 10 with an updation statement j++. The second  for loop is used to print  * in the respective column (the value of j represents the column number). It is having a print statement System.out.println("* ") to print * in each column(for convenience, I've added a space for better visibility of columns in the output). The first for loop is used to define rows( the value of i represents the row number). It is having a print statement System.out.print() to change rows each time the second for ...

Binary Search | The-Algorithm-Drive | MyCodingNetwork

Binary Search The next algorithm, we are going to study is Binary Search . As the name suggests, it is a searching algorithm. It is one of the very famous searching techniques. Unlike its counterpart linear search, it is way more advanced.  Time complexity of linear search is O(N) whereas that of binary search is O (log N). Source Code: Output Number Found at index =5 Working Let’s come on to the working of the algorithm, as you can see in the above program, we need a sorted array to perform binary search algorithm. 1.    Here, bin function in the above program it accepts 4 parameters, that is, the array arr , lower index low , higher index high and the searching number sn . 2.    Next, we have a do-while loop to check if high is greater than or equal to low (high>=low). If at any point of iteration this condition is not satisfied, it means the searching number sn does not exist in the array. Following is the algorithm for binary search: while ...