I am generating 100,000 random numbers and passing to the sorting function. The numbers are random, meaning that the time taken to sort the array should be more than the best case and less than the worst case. (pardon me if I am wrong, still learning time complexity). It took 25 seconds.
Then, I am passing the same sorted array again to sort function, and it took nearly 0 seconds.
Then, I am reversing the array, thus it should take the maximum number of iteration (swapping) and therefore should take more than 25 seconds of average time complexity. However, it is taking only 8 seconds.
public class BubbleSort {
private static void sort(int arr[]) {
int n = arr.length;
int temp = 0;
boolean sorted = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
sorted = false;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(sorted) {
break;
}
}
}
public static void main(String[] args) {
int arr[] = new int[100000];
Random rand = new Random();
for (int i = 0; i < 100000; i++) {
arr[i] = rand.nextInt(10000000);
}
// Avg Case
long x = System.currentTimeMillis();
sort(arr);
long y = System.currentTimeMillis();
float sec = (y - x) / 1000F;
System.out.println("avg Case " + sec);
// Best Case
x = System.currentTimeMillis();
sort(arr);
y = System.currentTimeMillis();
sec = (y - x) / 1000F;
System.out.println("Best Case " + sec);
// Worst Case
reverse(arr);
x = System.currentTimeMillis();
sort(arr);
y = System.currentTimeMillis();
sec = (y - x) / 1000F;
System.out.println("Worst Case " + sec);
}
}
Here's the output:
avg Case 25.207 Best Case 0.0 Worst Case 8.896
