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.