Bubble Sort Analysis

In this post I wanted to put down the information I have gathered from the analysis of Bubble sort.

Java program used:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

import java.util.Random; import java.util.Scanner; public class Class1 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n=scanner.nextInt(); int[] arr=new int[n]; Random random = new Random(); for (int i=0;i<n;i++) arr[i]=random.nextInt(n); scanner.close(); long startTime = System.nanoTime(); for (int i=0;i<arr.length;i++) { boolean flag=false; for (int j=0;j<arr.length-i-1;j++){ if (arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; flag=true; } } if (!flag) break; } System.out.println("time taken: "+(double)((System.nanoTime()-startTime))/1000000000); } }

In the above program, I have only considered the start time as the one just before the sorting started and the end time likewise.

Data:

Record count	Time taken in seconds
199	0.001364608
699	0.010424671
999	0.013886809
3999	0.03367852
6999	0.094484978
9999	0.20464032
39999	2.708212326
49999	4.271805616
99999	17.222403548
399999	299.15396555

Graph:

The following graph plotted takes the function O(n^2).

Bubble sort has the worst case and average case complexity of O(n^2).

Source: Bubble Sort Wiki

Please do comment on any discrepancy in my analysis.

Implementation of Euclidean Algorithm in Java

In this post, I am going to share the implementation of Euclidean Algorithm in Java.

Euclidean Algorithm is nothing but a method for calculating GCD of two numbers.

GCD (Greatest Common Divisor) : 

Take two numbers 20 and 30.

Factors of 20: 1, 2, 4, 5, 10, 20.

Factors of 30: 1, 2, 3, 5, 6, 10, 15, 30.

GCD refers to highest common factor of two numbers.

Now for 20 and 30, the common factor and the highest number is: 10. So GCD for 20 and 30 is 10.

The essence of this post is how can we calculate GCD in Java.

Well here it goes,

1:  import java.util.Scanner;  
2:  public class EuclideanAlgo {  
3:       public EuclideanAlgo() {  
4:       }  
5:       public static void main(String[] args) {  
6:            EuclideanAlgo euclideanAlgo = new EuclideanAlgo();  
7:            // Scanner class is used to values in the run time.  
8:            Scanner scanner = new Scanner(System.in);  
9:            // Below takes value of variable a.  
10:            System.out.println("Enter value for a: ");  
11:            int a = scanner.nextInt();  
12:            // Below takes value of variable b.  
13:            System.out.println("Enter value for a: ");  
14:            int b = scanner.nextInt();  
15:            // Calling method returnGCD to get GCD from there.  
16:            int gcd = euclideanAlgo.returnGCD(a, b);  
17:            System.out.println("GCD of " + a + " and " + b + " is: " + gcd);  
18:       }  
19:       private int returnGCD(int a, int b) {  
20:            if (b == 0)  
21:                 return a;  
22:            else {  
23:                 return returnGCD(b, a % b);  
24:            }  
25:       }  
26:  }  

Results are as follows:

In the above code, I used a Scanner class instance in lines 10 and 12 to record values of variables a and b at runtime and passed the values to a function in line 16.

The function returnGCD does the following:

Let's take value of a as 20 and b as 30.

Here 

The function is a recursive one and loops until it finds the second argument of the function to be 0.

If the second argument is not 0, it enters else and the arguments for the method becomes b and a%b.

Explantaion:

For example a is 20 and b is 30.

If condition is false since b is not 0.
Enters else and method is again called with arguments as 
a = 30 (b) and b = 20%30 (a%b) = 20.

If condition is false since b is not 0.
Enters else and method is again called with arguments as 
a = 20 (b) and b = 30%20 (a%b) = 10.

If condition is false since b is not 0.
Enters else and method is again called with arguments as 
a = 10 (b) and b = 20%10 (a%b) = 0.

Now this is a hit!

Code enters If and exits the method with value 10 which is GCD of 20 and 30.