I'm currently doing a sorting project where we have to implement random arrays for 10, 100, 1000, 10000, and 100000 elements per sorting algorithm. I've created a method to generate the arrays and I've done some of the sorting methods in order to calculate clock times, array access times, and comparison times. I'm running into a problem with a few of my algorithms. For the one method algorithms like bubble sort and selection sort, I was fine. But when I got into merge sort and quick sort, I see some issues popping up. Can someone please take a look at what I've done wrong?
quicksort with insertion sort
The issue popped up with QuickSort alone as well.
This is how I'm calling it in the main method
Your array access and comparison times are far below the granularity of milliseconds. I don't think you can capture this with nano seconds. In general, to measure the performance of something that something must be run many times and the overall difference in time calculated and divided by the number of times run. In your setup you can do this for any sort method but not the array times within the methods.
If you really want to get tangled up in your underwear take a look at the Time Stamp Register. It's a 64 bit register that counts clock ticks. Back in the day it was a great way to get nanosecond resolution. Then some perverted boffins invented stuff like multiple cores, threads, and CPUs that could adjust their clock frequency based on demand. If you're clever you can work around these, I'm not that clever.
If you want I might still have some C++ code I wrote about 20 years ago that uses the register, I'd just have to dig around to find it.
Then again, I have no idea how you could read a hardware register in Java.
Caveat: I haven't looked at this register in 20 years, I'm not even sure it still exists in modern CPUs. It may also be Intel specific.
I would suggest a few things for simple performance testing:-
1: If you are doing anything beyond the most basic and simplest timings, get yourself a profiler program.
2: You have an optimising compiler and runtime. Before you try any timings, be sure to run all the code you are going to test, so you get > 10,000 iterations. For example, sort a few 1,000,000 element arrays before you test anything. That will encourage the JVM to implement all the optimisations.
3: Timings are not exact, and vary. I have found cses where alorithm A runs 10% faster than algorithm B 75% of the time, and the other 25% of the time alorithm B is 10% faster! Ignore any differences that small.