Selection Sort timing

Question

I wrote a quick selection sort program shown below:

public static ArrayList<Integer> selectionSort(ArrayList<Integer> list) {
        for (int i=0; i < list.size()-1; i++) {
            int smallestElement = i;
            for (int j=i+1; j < list.size(); j++) {
                if (list.get(j) < list.get(smallestElement)) {
                    smallestElement = j;
                }
            }
            swapPosition(list, smallestElement, i);
        }

        return list;
    }

    public static void swapPosition(ArrayList<Integer> list, int first, int second) {
        Collections.swap(list, first, second);
    }

In my main program, I calculate the time the program takes to run in milliseconds. I created a new ArrayList of 1000 items that are already sorted and calculated the best case scenario time. I then reversed the order of the 1000 items to signify the worst case scenario when all the items must be swapped, but my worst case scenario takes less time than my best case for some reason. In the best case, nothing should have to be swapped. Why is my program taking more time to run in the best case than in the worst case? Here is the code for the rest:

ArrayList<Integer> bestCase = new ArrayList<Integer>();
        for (int i=1; i < 1001; i++) {
            bestCase.add(i);
        }
        long startTimeBest = System.currentTimeMillis();
        selectionSort(bestCase);
        long endTimeBest = System.currentTimeMillis();
        long totalTimeBest = endTimeBest - startTimeBest;
        System.out.println("Total time of this program in the best case "
                + "scenario is: " + totalTimeBest + " millisecond(s)");

        Collections.reverse(bestCase);
        long startTimeWorst = System.currentTimeMillis();
        selectionSort(bestCase);
        long endTimeWorst = System.currentTimeMillis();
        long totalTimeWorst = endTimeWorst - startTimeWorst;
        System.out.println("Total time of this program in the worst case "
                + "scenario is: " + totalTimeWorst + " millisecond(s)");

The time for the best case is 16 ms and the worst case is 4 ms. This doesn't make sense.

Start here: http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — NPE, Sep 20 '14 at 18:15
Your benchmark is bunk. Try for example inverting the order of the tests. — Diego Basch, Sep 20 '14 at 18:37

score 1 · Answer 1 · answered Sep 20 '14 at 19:04

Apart from issues with testing techniques, there seems to be another problem.

"I then reversed the order of the 1000 items to signify the worst case scenario when all the items must be swapped, but my worst case scenario takes less time than my best case for some reason. In the best case, nothing should have to be swapped."

In your program, the number of swaps (swapPosition(...) calls) executed does not depend on the order of the elements to be sorted.

The number of smallestElement = j; instructions executed does depend on the order.

Selection Sort timing

1 Answers1