Big O Sorts
number of comparisons, number of swaps, big o complexity, and total time for insertion sort
public class InsertionSort {
public int comparisons = 0;
public int swaps = 0;
public static void main(String[] args) {
long start = 0; //
long end = 0;
// create a new InsertionSort object
InsertionSort insertionSort = new InsertionSort();
for (int i=0;i<12;i++) {
// generate 5000 random elements
int[] array = new int[5000];
for (int j=0;j<5000;j++) {
array[j] = (int)(Math.random()*10000);
}
// sort the array
start += System.currentTimeMillis();
insertionSort.sort(array);
end += System.currentTimeMillis();
}
// get average
System.out.println("Average time taken: " + (end-start)/12 + " ms");
System.out.println("Average comparisons: " + insertionSort.comparisons/12);
System.out.println("Average swaps: " + insertionSort.swaps/12);
}
public void sort(int[] numbers) {
for (int i = 1; i < numbers.length; ++i) {
int key = numbers[i];
int j = i - 1;
while (j >= 0 && numbers[j] > key) {
numbers[j + 1] = numbers[j];
j = j - 1;
this.comparisons++;
this.swaps++;
}
numbers[j + 1] = key;
this.swaps++;
}
}
}
InsertionSort.main(null);
public class MergeSort {
public int comparisons = 0;
public int swaps = 0;
public static void main(String[] args) {
long start = 0;
long end = 0;
// create a new MergeSort object
MergeSort mergeSort = new MergeSort();
for (int i=0;i<12;i++) {
// generate 5000 random elements
int[] array = new int[5000];
for (int j=0;j<5000;j++) {
array[j] = (int)(Math.random()*10000);
}
// sort the array
start += System.currentTimeMillis();
mergeSort.sort(array);
end += System.currentTimeMillis();
}
// get average
System.out.println("Average time taken: " + (end-start)/12 + " ms");
System.out.println("Average comparisons: " + mergeSort.comparisons/12);
System.out.println("Average swaps: " + mergeSort.swaps/12);
}
public void sort(int[] arr) {
if (arr.length <= 1) {
return;
}
// Divide the array in half
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
// Recursively sort each half
sort(left);
sort(right);
// Merge the sorted halves
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
this.comparisons++;
if (left[i] <= right[j]) {
this.swaps++;
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
// Copy remaining elements from left or right subarray
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
}
MergeSort.main(null);