Sorting Implementation, same test case

Question

i have sth like: ( X - different algorithms)

public class XAlgorithm{
 sort(List l){...}
}

In testClass it present as follows:

ArrayList array = new ArrayList(...); // original array

public static void main(String[]args){

    AlgorithmsTest at = new AlgorithmsTest();
    at.testInsertSort();
    // when add at.array.printAll() - method printing all elements, there are no changes to original array what I want
    at.testBubbleSort();
    at.testSelectSort();
    at.testShellSort(); 

}



 testBubbleSort{
    ...
    ArrayList arrayBubble = new ArrayList(testBubble.sort(array));
    ...
}

Problem is my result ( time measured by System.currentTimeMilis() ) is different when i launch for ex. two times in a row the same algorithm, it's also strange because even when I done copying in every method ( by putting all new Elements into new array and then operate on it) still works wrong. Time is always greatest for first algorithm in main no matter which one it is.

I even controlled array between every algorithm ( like //comment in code above) and it is right - no changes to it, so where is the problem :/ ?

Thanks in advance

Possible duplicate of [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Tom, Apr 05 '16 at 00:32
Unfortunately I don't see any connection, that code isn't that complicated. — kolboc, Apr 05 '16 at 00:42

score 0 · Answer 1 · answered Apr 05 '16 at 00:45

0

Even though you stated you're making a copy of the array, it sounds like you're sorting in place and then making a copy of the array.

Therefore, the first time is going to take longest, but all subsequent runs have less work to do because the array is "sorted".

It also seems to say that your sort algorithms have bugs in it, such that you're getting close on the first sort (or it is right) but then a subsequent sort is finding a corner case, causing a slight variation in the sorted array. I'd be analyzing my sort methods and make sure they're working as you intended.

answered Apr 05 '16 at 00:45

Scott Sosna

1,443
1
8
8

I also tested them one by one and they work fine. I cannot catch the copy mistake, cause with copy and without it when I'm controlling it by printing out all elements after every singe sortAlgorithm there is no change to the array, so it let me thinks original array is passed to next sortAlgorithm. – kolboc Apr 05 '16 at 00:49
With what you've given us, that's what I think is happening, don't know what else to tell you. Perhaps have a method in AlgorithmTest that creates a fresh array for each call and make sure the array is fresh each and every time (even if the elements are in the identical order) because non-deterministic sort algorithms are not sort algorithms. – Scott Sosna Apr 05 '16 at 00:53
`(private ArrayList copyOfArray(ArrayList array){ Object[]copyArray = new Object[array.size()]; for(int i = 0; i < copyArray.length; i++){ copyArray[i] = new Car((Car)array.get(i)); } ArrayList copy = new ArrayList(copyArray); return copy; }` Is that copy method right ? – kolboc Apr 05 '16 at 01:07

Sorting Implementation, same test case

1 Answers1