javaalgorithmsortingblack-box-testing

Java, sorting analysis. Heapsort, Quicksort1, Quicksort2, Mergesort, given a blackbox


I was given a class in Java called BlackBox.java. There are four types of sorting methods in this class and they are called sort1, sort2, sort3 and sort4. It is given that we have Mergesort, Heapsort, Quicksort with the first place in the array as pivot (does not use StdRandom.shuffle), and finally we have Quicksort which take the middle of first and last elements and use that as pivot (also does not use StdRandom.shuffle).

The problem is that I need to find out which sorting method (sort1, sort2, sort3, sort4) is what. I have already counted the time with input of 500.000 integers. First I used random ordered input, than I used input sorted regularly and than I used input sorted reverse and finally I used a really big input with the same integer, 3 everywhere ({3 3 3 3 3...}). Sometimes I got stack overflow and sometimes not. I also got very similar sorting time for all of them, I mean very similar that I was not able to use it to tell which sorting algorithm I was using.

How can I find out which algorithm is what? What methods should I use?

P.s. I have already read chapter 1.4 in the book Algorithms written by Sedgewick and wayne and done alot of search on the internet. Maybe I am not understanding chapter 1.4 enough. So, I ask you to help me with this problem if you can.

Also, I am not aloud to check the bytecode.


Solution

  • there are 3 main differences between all these algorithms:

    1. order preserving (stable/unstalbe)
    2. order in which different objects are compared to each other (or pivot)
    3. order in which different objects are swapped

    to test for order preserving you need to sort objects with one property to sort on and second one to distinguish them, for example:

    class item {
      int sortid;
      string name;
    
      compareTo(item) -> return compare(this.sortid, item.sortid); note that name is not used
    }
    

    so, by supplying array, which have non-unique sortid, but different names you can check algorithms for stability, note - you need to use multiple inputs to see stability, as even non-stable ones could return stable order:

    different implementation of quick sorts will first try to move objects smaller to pivot to the left and greater to right, so if you find that your elements are compared with first element - it is first implementation of pivot, if with middle - it is second implementation of quick sort

    to implement this, you need to pass objects with custom comparison, which will check which element they are compare to and they know what can be used as pivot, so first comparison will give you answer which pivot is actually used by which sort method

    at this point it will be clear which one is heap, but if you have ability to monitor element swaps, you can also detect heap, as it starts putting smallest/largest elements first