# Count the number of checks each method had to perform before fully sorting the array

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;
}
}

• What are you countng? Comparisons or swaps? Right now it looks like your counts are not counting either one correctly.
– JS1
Feb 20, 2016 at 3:13
• Well I'm trying to count how many times it takes to a sort an array, but I think I'm just going to end up doing comparisons. I moved the bubbleCount right above the if statement, moved the mergeCount into the merge method in the first while loop, and then I moved the quickCount into the partition method where a[i] is < or > the pivot. So hopefully that is right. @JS1 Feb 20, 2016 at 3:24
• Welcome to Code Review! Please declare your cross-post. Feb 20, 2016 at 4:36

### Magic number

20 - the number of iterations - should be replaced with a static final variable, so that you can freely modify the number of iterations to perform.

### Printing arrays

Arrays.toString(int[]) gives you a nice String representation for printing to the console, so you do not have to loop yourself.

### Too much static

You are currently using too many static variables to store your data and counts, and that can make it unwieldy.

### An alternative modeling approach

How about considering that each test should implement an interface that provides a count of every run, and other useful metrics?

public interface Sorter {

/**
* Sorts an array.
*
* @param the array to sort
* @return the number of steps it takes to sort an array
*/
int sort(int[] array);

/**
* Gets the number of method calls to {@link #sort(int[])} so far.
*
* @return the number of iterations done
*/
int getIterations();

/**
* Gets the total sorting count so far.
*
* @return the total number of sorting steps done
*/
long getTotalCount();
}


Then you can have implementations...

public class BubbleSorter implements Sorter {

int iterations = 0;
long totalCount = 0;

@Override
public int sort(int[] array) {
int countResult = 0;
// do sorting while calling countResult++ where appropriate
iterations++;
totalCount += countResult;
return countResult;
}

@Override
public int getIterations() {
return iterations;
}

public long getTotalCount() {
}
}


You can then rely on the methods to give you your results.

public static void main(String[] args) {
Sorter bubbleSort = new BubbleSorter();
int lastCount = 0;
for (int i = 0; i < ITERATIONS; i++) {
lastCount = bubbleSort.sort(getNewRandomArray());
}
System.out.println("Last count: " + lastCount);
System.out.println("Average: " +
((bubbleSort.getTotalCount() * 1.0) / bubbleSort.getIterations());
}


Note that this simplified approach does not take multi-threading into consideration. With some slight tweaks to how iterations and totalCount can be accumulated in a thread-safe manner, making calls to each sorting algorithms' sort() method concurrently to reduce execution time is certainly achievable.