In this post I wanted to put down the information I have gathered from the analysis of Bubble sort.
Java program used:
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:
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.
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.