Help with comparison counters in quick sort algorithm

At the suggestion of @templatetypedef, I am posting the code for my quick sort to see if anyone can offer suggestions as to where to make comparisons. And any tips on improving the code. I am using this in conjunction with a Merge Sort and Heap sort to see how the different comparison algorithms sort an array of random numbers.

I will post my Merge Sort and heap sort in other posts so they stay separate based on tips from @templatetypedef. I actually have them all in a package that runs them together but separating them out for clarity.

```
package AlgorithmComparison;

import java.util.*;
import java.math.*;

public class AlgCompareApp
{

public static void main(String[] args)
{
int qSortCnt = 0;
int numbersNeeded = 5000; // Number in the array
double total = logb(numbersNeeded, 2);
double logN = numbersNeeded * total;
int loopCount = 50; // Change this for the Loop through each sort

System.out.print("n log(n) for " + numbersNeeded + " is ");
System.out.printf(" %.2f", logN);
System.out.println();

System.out.println("Quick Sort");
for (int l = 0; l arrlist = new ArrayList();

// Populate Initial Array List with numbers and no duplicates
for (int i = 0; i < numbersNeeded; i++)
{
while (true)
{
Integer next = rng.nextInt(numbersNeeded * 2);
if (!arrlist.contains(next))
{
arrlist.add(next);
break;
}
}
}

// Create QuickSort Int Array from ArrayList
int[] quickSortArray = new int[arrlist.size()];
for (int i = 0; i < arrlist.size(); i++)
{
quickSortArray[i] = arrlist.get(i);
}

// QUICK SORT RUN
//System.out.print("\n---------------Quick Sort---------------\n");
QuickSortRun qksrt = new QuickSortRun(quickSortArray, numbersNeeded);
qksrt.quickSort();
qSortCnt = qSortCnt + qksrt.getComparisons();
qksrt.displayComparisons();
}
Sys

I'll review the testing procedure here. The main() function is long enough to be worth breaking up.

If you intend to test several sorting algorithms, then the algorithms should all implement a common interface so that they are interchangeable.

public interface SortingAlgorithm {
    public void sort(int[] array);
}

public class QuickSort implements SortingAlgorithm {
    @Override
    public void sort(int[] array) {
        // Quicksort implementation
    }
}

public class MergeSort implements SortingAlgorithm {
    @Override
    public void sort(int[] array) {
        // Mergesort implementation
    }
}

Then you would be able to use the same driver to test all of them.

public class AlgCompareApp {
    private SortingAlgorithm[] algorithms;
    private long[] times;

    public AlgCompareApp(int arraySize, SortingAlgorithm[] algorithms) {
        this.algorithms = algorithms;
        this.times = new long[algorithms.length];
    }

    public void run(int iterations, int arraySize) {
        for (int i = 0; i < iterations; i++) {
            int[] array = generateRandomArray(arraySize);
            for (SortingAlgorithm alg : this.algorithms) {
                this.times[i] += measureSortingAlgorithm(alg, array);
            }
        }
    }

    public void displayStatistics() {
        // TODO
    }

    private static int[] generateRandomArray(int size) {
        // TODO
    }

    private static long measureSortingAlgorithm(SortingAlgorithm alg, int[] array) {
        array = Arrays.copyOf(array, array.length);
        long startTime = System.nanoTime();
        alg.sort(array);
        long finishTime = System.nanoTime();
        return finishTime - startTime;
    }

    public static void main(String[] args) {
        SortingAlgorithm[] algorithms = new SortingAlgorithm[] {
            new QuickSort(),
            new MergeSort(),
            new HeapSort()
        };
        AlgCompareApp app = new AlgCompareApp(algorithms);
        app.run(50, 5000);
        app.displayStatistics();
    }
}

Your procedure for generating random arrays of distinct elements is inefficient, both because you attempt to filter out duplicates (towards the end, each number will collide with near 50% probability), and because you search for duplicates by linear traversal of the array (which takes O(n2) time in total). I'm not sure why you want to weed out duplicates, as the ability of sorting algorithms to handle duplicate entries is important to test too. If you do want all array elements to be distinct, you might as well use consecutive numbers. (Comparison-based sorts shouldn't care how large the gaps are between numbers.) If you really want to achieve your original goal, you could put 2 n consecutive numbers in an array, apply a Fisher-Yates shuffle, then truncate it to n elements.

StackExchange Code Review Q#27495, answer score: 3