current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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 < loopCount; l++)
    {
      Random rng = new Random();
      // Create initial Array List of numbers
      ArrayList<Integer> arrlist = new ArrayList<Integer>();

      // 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();
    }
    System.out.println("Averages");
    System.out.println((qSortCnt / loopCount));
    System.out.println("Percentage of n log(n)");
    System.out.printf("%.2f", ((qSortCnt / loopCount) / logN));
    System.out.println();
  }

  public static double logb(double a, double b)
  {
    return Math.log(a) / Math.log(b);
  }
}


package AlgorithmComparison;

import java.util.*;

public class QuickSortRun {

    private int[] theArray;
    private int nElms;
    private int comparisons;

    public QuickSortRun(int[] max, int n){
        theArray = max;
        nElms = n;
    }

    public void insert(int value){
        theArray[nElms++] = value;

    }

    public void display(){
//        for(int i = 0; i < nElms; i++){
//            System.out.print(theArray[i] + " ");
//        }
//        System.out.println(" ");
    }

    public void displayComparisons(){
        System.out.println(comparisons);
    }

    public void reverseArray(){

        int left = 0;
        int right = theArray.length - 1;

        while(left < right){
            int temp = theArray[left];
            theArray[left] = theArray[right];
            theArray[right] = temp;

            left++;
            right--;
        }
    }

    private void swap(int dx1, int dx2){
        int temp = theArray[dx1];
        theArray[dx1] = theArray[dx2];
        theArray[dx2] = temp;
        comparisons++;
    }

    private int medianOf3(int left, int right){

        int center = (left +right)/2;

        if(theArray[left] > theArray[center])
            swap(left, center);
        if(theArray[left] > theArray[right])
            swap(left, right);
        if(theArray[center] > theArray[right])
            swap(center, right);

        swap(center, right);
        return theArray[left];
    }

    public void quickSort(){
        comparisons = 0;
        recQuickSort(0, nElms-1);
    }

    private void recQuickSort(int left, int right){
        int size = right-left+1;

        if(size < 5)
            insertionSort(left, right);
        else
        {
            int median = medianOf3(left, right);
            int partition = partitionIt(left, right, median);
            recQuickSort(left, partition-1);
            recQuickSort(partition+1, right);
        }
    }

    private int partitionIt(int left, int right, int pivot){

        int leftPtr = left-1;
        int rightPtr = right;

        while(true){
            while(theArray[++leftPtr] < pivot);
            while(theArray[--rightPtr] > pivot);
            if(leftPtr >= rightPtr)
                break;
            else
                swap(leftPtr,rightPtr);
        }
        swap(leftPtr, right);
        return leftPtr;
    }

    private void insertionSort(int left, int right){
        int in, out;

        for(out = left + 1; out <= right; out++){
            int temp = theArray[out];
            in = out;
            while(in > left && theArray[in-1] >= temp){
                theArray[in] = theArray[in-1];
                in--;
            }
            theArray[in] = temp;
            comparisons++;
        }
    }

  public int getComparisons()
  {
    return comparisons;
  }
}

My entire Java package is zipped up and can be downloaded from here.

share|improve this question

1 Answer 1

up vote 3 down vote

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.

share|improve this answer
    
+1 for bonus tips on generating a shuffled starting array. –  David Harkness Jan 19 '14 at 23:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.