BUBBLE SORT CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

Example :

public class Sort {

void bubbleSort(int arr[]) {

int n = arr.length;
int temp;
for (int i=0; i < n-1; i++) {

//(n-i-1) is to ignore the comparisons that is already done.

for(int j = 0; j < n-i-1; j++) {

if(arr[j] > arr[j+1] ) {

temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

public static void main(String args[]) {
int arr[] = {7, 4, 8, 1, 6};

Sort sort = new Sort();
sort.bubbleSort(arr);

for(int i=0; i < arr.length; i++) {

System.out.print(arr[i]+", ");
}
}
}

We are just concerned about the 'void bubbleSort(int arr[])' method, where the sorting logic is defined.

We have the array

int arr[] = {7, 4, 8, 1, 6};

Which we have passed to the 'bubbleSort(..)' method.

In the 'bubbleSort(..)' method, we have taken the count of the elements of the array.

int n = arr.length;

Now, let us corelate this code with the explanation of Bubble Sort.

Let us take the same diagram.

And take the chunk of code and explain it.

for (int i=0; i < n-1; i++) {

for(int j = 0; j < n-i-1; j++) {

if(arr[j] > arr[j+1] ) {

temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

So, the outer loop, i.e.

int n = arr.length;

Determines the Passes. If you see the above explanation you can find the first pass,

1st Pass (i.e. When i=0)

Then comes the the inner loop, i.e.

for(int j = 0; j < n-i-1; j++)

Which determines the iterations.

Next, Comes the comparison where we compare 1st and 2nd element. And if the 1st element is greater than 2nd element we swap it.

if(arr[j] > arr[j+1] ) {

temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}

Where arr[j] refers to the first element i.e. 7 and arr[j+1] refers to the second element i.e. 4.

And continue in the same pattern.

Note : (n-i-1) in the conditional part of inner loop ignores the last element from each passes.

Efficiency / Running time of Bubble Sort

If we consider the Bubble Sort Algorithm, there are two loops. Firstly, there is the 'for' loop.

And inside the 'for' loop there is also a 'for' loop.

The 'for' loop executes n times(Assuming the array contains n elements).

Now, for each iteration of 'for' loop, the nested 'for' loop also executes approximately 'n' times.

Which means for 1st iteration of 'for' loop,

the nested 'for' loop also runs n time.

Similarly, for 2nd iteration of 'for' loop,

inner 'for' loop runs (n-1) times.

Similarly, for nth iteration of 'for' loop,

inner 'for' loop runs 1 time.

So, the running time is close to n*n or n^2.

So, in worst case the running time is O(n^2).

Note : Worst case is the scenario where the array elements are all sorted in descending order. i.e. 8, 7, 6, 4, 1.

❮❮ PREV NEXT ❯❯