So I'm writing a program that compares Bubble, Selection, Merge, and Quick Sort. All 4 methods are given a randomized array of 1000 elements and I count to see how many times it takes a method to perform to fully sort the array. My question revolves around the placement of my counts. I know I should look at the Big O complexities for each to get a ballpark estimate of the number but I'm just asking if I put the counts in the right spots.
import java.util.*;
public class SortingComparison1
{
//Creates class variables
static Random random = new Random();
static int bubbleCount = 0;
static int totalBubbleCount = 0;
static int totalSelectionCount = 0;
static int totalMergeCount = 0;
static int totalQuickCount = 0;
static int mergeCount = 0;
static int selectionCount = 0;
static int quickCount = 0;
static int [] arr;
static int [] copyArr;
static int [] copyArr2;
static int [] copyArr3;
public static void main(String[] args)
{
System.out.println("Welcome to the sort tester.");
//runs this 20 times
for(int i = 0; i <20; i++)
{
//assigns array arr to the gen array method
arr = generateRandomArray();
//creates copy arrays and copies the arr array
copyArr = Arrays.copyOf(arr, arr.length);
copyArr2 = Arrays.copyOf(arr, arr.length);
copyArr3 = Arrays.copyOf(arr, arr.length);
//Call each method for the different sorts
System.out.println();
bubble();
System.out.println();
selection();
System.out.println();
merge();
System.out.println();
quick();
}
System.out.println();
System.out.println("The average number of checks were:");
System.out.println("Bubble Count " + (totalBubbleCount / 20));
System.out.println("Selection Count " + (totalSelectionCount / 20));
System.out.println("Merge Count "+ (totalMergeCount / 20));
System.out.println("QuickSort Count " + (totalQuickCount / 20));
}
public static void bubble()
{
//assigns int[]a to arr
int[] a = arr;
System.out.println("Array Before Bubble Sort");
for (int i = 0; i < a.length; i++)
{
//Prints out unsorted array
System.out.print(a[i] + " ");
}
//sorts array with bubble sort method
bubbleSort(a);
System.out.println("");
System.out.println("Array After Bubble Sort");
for (int i = 0; i < a.length; i++)
{
//Prints out bubble sorted array
System.out.print(a[i] + " ");
}
System.out.println();
//Prints out number of checks to sort array
System.out.println("Bubble checks: " + bubbleCount);
totalBubbleCount += bubbleCount;
//resets bubbleCount
bubbleCount = 0;
}
public static void selection()
{
// assigns int[] a to the copied array
int[] a = copyArr;
System.out.println("Array Before Selection Sort");
for (int i = 0; i < a.length; i++)
{
//Prints out unsorted array
System.out.print(a[i] + " ");
}
//sorts int[] a with selection sort
selectionSort(a);
System.out.println("");
System.out.println("Array After Selection Sort");
for (int i = 0; i < a.length; i++)
{
//Prints out selection sorted array
System.out.print(a[i] + " ");
}
System.out.println();
//Prints out number of selections counts
System.out.println("Selection checks: " + selectionCount);
totalSelectionCount += selectionCount;
//resets selectionCount
selectionCount = 0;
}
public static void merge()
{
//assigns int[] a to second copied array
int[] a = copyArr2;
System.out.println("Array Before Merge Sort");
for (int i = 0; i < a.length; i++)
{
//Prints unsorted array
System.out.print(a[i] + " ");
}
//sorts array with mergeSort method
mergeSort(a);
System.out.println("");
System.out.println("Array After Merge Sort");
for (int i = 0; i < a.length; i++)
{
//Prints out merge sorted array
System.out.print(a[i] + " ");
}
System.out.println();
//Prints out number of checks
System.out.println("Merge checks: " + mergeCount);
totalMergeCount += mergeCount;
//resets mergeCount
mergeCount = 0;
}
public static void quick()
{
//assigns int[] a to third copied array
int[] a = copyArr3;
System.out.println("Array Before Quick Sort");
for (int i = 0; i < a.length; i++)
{
//Prints out unsorted array
System.out.print(a[i] + " ");
}
//sorts array by calling quickSort method
quickSort(a, 0, a.length - 1);
System.out.println("");
System.out.println("Array After Quick Sort");
for (int i = 0; i < a.length; i++)
{
//Prints out quick sorted array
System.out.print(a[i] + " ");
}
System.out.println();
//prints out quickCount and resets quickCount back to 0
System.out.println("QuickSort checks: " + quickCount);
totalQuickCount += quickCount;
//prints avg num of checks
quickCount = 0;
}
private static int[] generateRandomArray()
{
//generates array of size 1000 and fill it with random numbers, 0-999
int size = 20;
int[] a = new int[size];
for (int i = 0; i < size; i++)
{
a[i] = random.nextInt(1000);
}
return a;
}
public static int[] bubbleSort(int[] a)
{
boolean done = false;
int n = a.length;
while(done == false)//runs n times
{
done = true;
for(int i = 0; i < n-1; i++)//runs n times
{
if(a[i] > a[i+1])//Swap
{
bubbleCount++;
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
done = false;
}
}
}
return a;
}
public static void mergeSort(int [] a)
{
//put counter for checks inside method
int size = a.length;
if(size < 2)//Halt recursion
{
return;
}
int mid = size/ 2;
int leftSize = mid;
int rightSize = size - mid;
int[] left = new int[leftSize];
int[] right = new int[rightSize];
//populate left
for(int i = 0; i < mid; i++)
{
mergeCount++;
left[i] = a[i];
}
//populate right
for(int i = mid; i < size; i++)
{
mergeCount++;
right[i-mid] = a[i];
}
mergeSort(left);
mergeSort(right);
//merge
merge(left, right, a);
}
public static void merge(int[] left, int[] right, int[] a)
{
int leftSize = left.length;
int rightSize = right.length;
int i = 0;//index for left
int j = 0;//index for right
int k = 0;//index for a
while(i < leftSize && j < rightSize)//compares until the end is reach in either
{
if(left[i] <= right[j])
{
//assigns a[k] to left[i] and increments both i and k
a[k] = left[i];
i++;
k++;
}
else
{
//assigns a[k] to right [j] and increments j and k
a[k] = right[j];
j++;
k++;
}
}
//fills in the rest
while(i<leftSize)
{
a[k] = left[i];
i++;
k++;
}
while(j<rightSize)
{
a[k] = right[j];
j++;
k++;
}
}
public static void selectionSort(int[] a )
{
for (int i = 0; i < a.length - 1; i++)
{
int pos = i;
for (int j = i + 1; j < a.length; j++)
{
// increments selection count
selectionCount++;
// if a[j] is less than a[pos], set pos to j
if (a[j] < a[pos])
{
pos = j;
}
}
// swaps a[i] and a[pos]
int temp = a[i];
a[i] = a[pos];
a[pos] = temp;
}
}
public static void quickSort(int[] a, int left, int right)
{
int index = partition(a, left, right);
if(left < index - 1)
{
//increments quickCount and calls quickSort recursively
quickCount++;
quickSort(a, left, index-1);
}
if(index < right)
{
//increments quickCount and calls quicSort recursively
quickCount++;
quickSort(a, index, right);
}
}
public static int partition(int[] a, int left, int right)
{
int i = left;
int j = right;
int pivot = a[((left+right)/2)];
while(i<=j)
{
while(a[i] < pivot)
{
i++;//correct position so move forward
}
while(a[j] > pivot)
{
j--;//correct position
}
if(i <= j)
{
//swaps and increments i and decrements j
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
return i;
}
}