Why am I getting linear run time with Quicksort?

Question

Update: I see what my problem is. I'm sorting 10000 datapoints every time. That will take the same time each iteration. t was my incorrect way of attempting to sort 100 of those datapoints, then add the next 100 datapoints, sort and so on.

I am trying to show that the average/best case running time for Quicksort is O(nlogn). However when I try to time the method over a large amount of cycles I get linear run time.

I assume it has something to do with the way I'm implementing the for loop, but I have no idea why it would be wrong.

I also have another function that reads an array already sorted to give me worst case run time, but that also gives me linear.

For both functions, the times look like this:

System.out.println("Enter the number of data points you want to sort as an integer: ");
Scanner num = new Scanner(System.in);
int datapoints = num.nextInt();
int[] dpArr = new int[datapoints];

for (int i = 0; i < datapoints; i++) 
{
    dpArr[i] = (int) (Math.random() * 100000);
}
int n = dpArr.length;

try 
{   
    PrintWriter pw = new PrintWriter(new FileWriter("random2.csv", true));
    StringBuilder sb = new StringBuilder();
    StringBuilder sb2 = new StringBuilder();

    for (int t = 100; t <= 100000; t += 100) 
    {
        long qstotal = 0;

        long start = System.nanoTime();
        quicksort(dpArr, 0, n - 1);
        qstotal += System.nanoTime() - start;

        double qsDuration = (double) qstotal / 1000000;
        sb.setLength(0);
        sb.append(t);
        sb.append(',');
        sb.append(qsDuration);          
        sb.append("\n");
        pw.write(sb.toString());
    }

    for (int t = 100; t <= 100000; t += 100) 
    {
        long rqstotal = 0;

        long start = System.nanoTime();
        randomQuicksort(dpArr, 0, n - 1);
        rqstotal += System.nanoTime() - start;

        double rqsDuration = (double) rqstotal / 1000000;
        sb2.setLength(0);
        sb2.append(t);
        sb2.append(',');
        sb2.append(rqsDuration);
        sb2.append("\n");
        pw.write(sb2.toString());
    }  
    pw.flush();          
    pw.close();

}
catch (FileNotFoundException e) 
{
    System.out.println("File not found.");
}

it is better to re-init dpArr every time you call sort function, otherway you're "sorting" already sorted array, ie do nothing — Iłya Bursov, Sep 28 '16 at 16:30
I don't really understand what this program is meant to be doing. You ask the user for a number of datapoints, they enter 24601. You generate 24601 data points, and then ... what's this business with `t`? What does `t` mean? You are sorting the 24601 data points 1000 times (but never re-initing the array as @Lashane points out), but why is `t` going up by 100 each time? What are you trying to measure, exactly? — dcsohl, Sep 28 '16 at 16:38
Upon further consideration... since you are sorting the same array 1000 times, and quicksort gives worst performance on already-sorted data, you can see this in your output: the first sort is much much faster (~2 ms) than all the others (~65 ms). — dcsohl, Sep 28 '16 at 16:43
I see what my problem is. I'm sorting 10000 datapoints every time. That will take the same time each iteration. `t` was my incorrect way of attempting to add the next 100 datapoints and then sort. — poniboy4, Sep 28 '16 at 16:52
@poniboy4: That is not the only problem. You have to do both the things - add more data points and run multiple runs to calculate the average for each number of data points. — displayName, Sep 28 '16 at 16:53
@poniboy4 If you found the solution, don't edit your post. Instead, **please post the solution as an answer and accept it** (it doesn't matter if it's your own answer). That way, other people can know that it is already solved and/or filter it out from the "unanswered" queue. — walen, Sep 28 '16 at 17:10

score 1 · Accepted Answer · edited May 23 '17 at 11:54

If you go by your current code, you will see that after first sorting, you are using the sorted array again. That is wrong.

To correct that, you can:

use a new random array (as @Lashane suggested); or,
use the same random array (i.e. in the same unsorted state that you started with) and use a different pivot; or,
shuffle the array after each call to quicksort(dpArr, 0, n - 1); and randomQuicksort(dpArr, 0, n - 1);.

I'd suggest going with the last option because you don't have to worry about modifying the pivots and you use the same values for each run (not that it really matters in a test for sorting time). To shuffle an array in Java, see this question.

Why am I getting linear run time with Quicksort?

1 Answers1