For CS homework assignment I am to create random arrays of increasing size in java and plot their runtime on a graph. However, my implementations of Insert, Merge, and Quick sort seem to have the same run times when run with the same input. I've implemented them differently many times and am still getting the same results. Here is my code:
import java.util.*; import java.util.Random;
public class Complexity {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input= new Scanner(System.in);
System.out.println("Enter the array size: ");
int a = input.nextInt();
System.out.println("Enter the number size: ");
int n = input.nextInt();
int[] arr = newArr(a, n);
int[] arr2 = arr.clone();
int[] arr3 = arr.clone();
//INSERT SORT
long startTime = System.nanoTime();
insertSort(arr);
long endTime = System.nanoTime();
long duration = (endTime - startTime)/1000000;
System.out.println("Insert Sort Time:" + duration + "ms");
//MERGE SORT
long start = System.nanoTime();
mergeSort(arr2, 0, a-1);
long end = System.nanoTime();
long dur = (end - start)/1000000;
System.out.println("Merge Sort Time:" + duration + "ms");
//QUICK SORT
long s = System.nanoTime();
quickSort(arr3, 0, a-1);
long e = System.nanoTime();
long d = (e - s);
System.out.println("Quick Sort Time:" + duration + "ms");
}
public static int[] newArr(int a, int n) {
Random rand = new Random();
int newArray[] = new int[a];
for (int i = 0; i < a; i++) {
int number= rand.nextInt(n);
newArray[i]=number;
}
return newArray;
}
public static void quickSort(int[] arr, int low, int high) {
if(low<high) {
int pivotIndex = findPivot(arr, low, high);
quickSort(arr, low, pivotIndex-1);
quickSort(arr, pivotIndex+1, high);
}
}
public static int findPivot(int[] arr, int low, int high) {
int pivot = arr[high];
int nextSmallest = (low-1);
for(int currentIndex = low; currentIndex < high; currentIndex++) {
if(arr[currentIndex] <= pivot) {
nextSmallest++;
int temp = arr[nextSmallest];
arr[nextSmallest] = arr[currentIndex];
arr[currentIndex] = temp;
}
}
int temp = arr[nextSmallest+1];
arr[nextSmallest+1] = arr[high];
arr[high] = temp;
return nextSmallest+1;
}
public static void mergeSort(int[] arr, int left, int right){
if(left<right) {
int middle = (left + right) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle+1, right);
merge(arr, left, middle, right);
}
}
public static void merge(int[] arr, int left, int middle, int right){
int leftLength = middle - left + 1;
int rightLength = right - middle;
int newL[] = new int [leftLength];
int newR[] = new int [rightLength];
for (int i=0; i<leftLength; ++i)
newL[i] = arr[left + i];
for (int j=0; j<rightLength; ++j)
newR[j] = arr[middle + 1+ j];
int i = 0, j = 0;
int k = left;
while (i < leftLength && j < rightLength) {
if (newL[i] <= newR[j]) {
arr[k] = newL[i];
i++;
}
else {
arr[k] = newR[j];
j++;
}
k++;
}
while (i < leftLength) {
arr[k] = newL[i];
i++;
k++;
}
while (j < rightLength) {
arr[k] = newR[j];
j++;
k++;
}
}
static void printArray(int arr[], String methodName) {
System.out.print(methodName);
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void insertSort(int[] arr){
int temp;
for(int i = 0; i < arr.length; i++) {
for(int j = i ; j > 0 ; j--){
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
}
