Return to Question

I have seen various tweaks for quicksort and to establish their usefulness, I designed a program that randomly generates arrays and times how long quicksort takes to sort them. Right now I'm focusing on how the pivot is chosen. I'm comparing choosing the first element as the pivot versus choosing the median of first, middle and last elements. I came across [an implementation][1] that presorts the first, middle and last element and have to implemented it for my tests.

• the index of the middle element is computed
• the 3 if statements rearange the first, middle and last element so they are in order relative to only each other (so for example 5,1,4,9,8 => 4,1,5,9,8). I am interested in the math behind how it is known that only 3 if statements are needed, since there are 3!(=6) permutations of 3 elements.
• the median is swapped so it's beside the largest valued element of the 3. Latter in the code I noticed partitionIt() has int rightPtr = right - 1; and I think the -1 is to avoid one extra iteration of the while loop as it's known [right-1] and [right] is a sorted sub array of size 2. Is this right? I don't really see how this benefits the algorithm as quicksort works on the principle of finding the final location of a pivot, and doesn't care a bout a sorted subarray.

Here is my code:

I'm not sure if I should be calling quicksort recusivley on quicksort(arr, beginning, partition); or quicksort(arr, beginning, partition-1);

I randomly generate arrays and call quicksort on them. The time is meausured and summed and at the end it is divided by the number of arrays that were tested (to give the average).

        long startTime = System.nanoTime();
        quicksort(randomArray, 0, randomArray.length-1);
        long endTime = System.nanoTime();
        totalTime += endTime-startTime; 

For the method of choosing the first element as the pivot and iterating through 1,000,000 arrays of length 100 with random values between [-100, 100] it took: 9498ns, 9464ns, 9459ns. Doing this on arrays of length 10 gave the times: 623ns, 670ns, 914ns, 838ns, 635ns. I ran extra tests as I was surprised to see such high variability. Why the variability?

For the tests run with the median with side effects implementation, on 1,000,000 randomly generated arrays of length 100 with values between [-100, 100] the results were: 8590ns, 8697ns, 8586 ns. For arrays of length 10 the results were: 655ns, 679ns, 660ns.

It doesn't look like choosing the pivot of median of 3, and presorting the 3, is much better than choosing the first element. In the future I'm going to write a pivot-choosing method that only takes the median of 3 and doesn't do the side-effect thing and see how fast it preforms. [1]: http://www.java2s.com/Tutorial/Java/0140__Collections/Quicksortwithmedianofthreepartitioning.htm

I have seen various tweaks for quicksort and to establish their usefulness, I designed a program that randomly generates arrays and times how long quicksort takes to sort them. Right now I'm focusing on how the pivot is chosen. I'm comparing choosing the first element as the pivot versus choosing the median of first, middle and last elements. I came across an implementation that presorts the first, middle and last element and have to implemented it for my tests.

• The index of the middle element is computed
• The 3 if statements rearange the first, middle and last element so they are in order relative to only each other (so for example 5,1,4,9,8 => 4,1,5,9,8). I am interested in the math behind how it is known that only 3 if statements are needed, since there are 3!  (=6) permutations of 3 elements.
• The median is swapped so it's beside the largest valued element of the 3. Latter in the code I noticed partitionIt() has int rightPtr = right - 1; and I think the -1 is to avoid one extra iteration of the while loop as it's known [right-1] and [right] is a sorted sub array of size 2. Is this right? I don't really see how this benefits the algorithm as quicksort works on the principle of finding the final location of a pivot, and doesn't care a bout a sorted subarray.

I'm not sure if I should be calling quicksort recursively on

quicksort(arr, beginning, partition);

or

quicksort(arr, beginning, partition-1);

I randomly generate arrays and call quicksort on them. The time is meausured and summed and at the end it is divided by the number of arrays that were tested (to give the average).

long startTime = System.nanoTime();
quicksort(randomArray, 0, randomArray.length-1);
long endTime = System.nanoTime();
totalTime += endTime-startTime; 

For the method of choosing the first element as the pivot and iterating through 1,000,000 arrays of length 100 with random values between [-100, 100] it took:

• 9498ns
• 9464ns
• 9459ns

Doing this on arrays of length 10 gave the times:

• 623ns
• 670ns
• 914ns
• 838ns
• 635ns

I ran extra tests as I was surprised to see such high variability. Why the variability?

For the tests run with the median with side effects implementation, on 1,000,000 randomly generated arrays of length 100 with values between [-100, 100] the results were:

• 8590ns
• 8697ns
• 8586ns

For arrays of length 10 the results were:

• 655ns
• 679ns
• 660ns

It doesn't look like choosing the pivot of median of 3, and presorting the 3, is much better than choosing the first element. In the future I'm going to write a pivot-choosing method that only takes the median of 3 and doesn't do the side-effect thing and see how fast it preforms.

/*returns index of element with median value of beginning, middle and end elements
sorts beginning, middle and end element relative to each other*/
private static int medianOf3(int[] arr, int beginning, int end) {
    int middle = (beginning + end) >>> 1;//>>> prevents overflow error where / wouldn't
    /*following 3 lines may cause side effects*/
    if(arr[beginning] > arr[middle])
        swap(arr, beginning, middle);
    
    if(arr[beginning] > arr[end])
        swap(arr, beginning, end);

    if(arr[middle] > arr[end])
        swap(arr, middle, end);
    
    swap(arr, middle, end-1);
    return arr[end-1];

}
    public static void qs(int[] arr, int beginning, int end) {

    if(end-beginning >= 1) {
        int partition = partition(arr, beginning, end);
        quicksort(arr, beginning, partition);//note sure if this should be partition-1
        quicksort(arr, partition + 1, end);
    }
}
private static int partition(int[] arr, int beginning, int end) {
    //int pivot = arr[beginning];
    int pivot = medianOf3(arr, beginning, end);
    int lftPtr = beginning-1;
    int rhtPtr = end+1-1;//-1 for last swap in median()
    for(;;) {
        lftPtr = lftPtr + 1;
        while(arr[lftPtr] < pivot && lftPtr < end)
            lftPtr = lftPtr + 1;
            
        rhtPtr = rhtPtr - 1;
        while(arr[rhtPtr] > pivot && rhtPtr > beginning)
            rhtPtr = rhtPtr -1;
            
        if(rhtPtr > lftPtr)
            swap(arr, lftPtr, rhtPtr);
        else
            return lftPtr;
    }
}

/*returns index of element with median value of beginning, middle and end elements
sorts beginning, middle and end element relative to each other*/
private static int medianOf3(int[] arr, int beginning, int end) {
    int middle = (beginning + end) >>> 1;//>>> prevents overflow error where / wouldn't
    /*following 3 lines may cause side effects*/
    if(arr[beginning] > arr[middle])
        swap(arr, beginning, middle);
    
    if(arr[beginning] > arr[end])
        swap(arr, beginning, end);

    if(arr[middle] > arr[end])
        swap(arr, middle, end);
    
    swap(arr, middle, end-1);
    return arr[end-1];

}
    public static void quicksort(int[] arr, int beginning, int end) {

    if(end-beginning >= 1) {
        int partition = partition(arr, beginning, end);
        quicksort(arr, beginning, partition);//note sure if this should be partition-1
        quicksort(arr, partition + 1, end);
    }
}
private static int partition(int[] arr, int beginning, int end) {
    //int pivot = arr[beginning];
    int pivot = medianOf3(arr, beginning, end);
    int lftPtr = beginning-1;
    int rhtPtr = end+1-1;//-1 for last swap in median()
    for(;;) {
        lftPtr = lftPtr + 1;
        while(arr[lftPtr] < pivot && lftPtr < end)
            lftPtr = lftPtr + 1;
            
        rhtPtr = rhtPtr - 1;
        while(arr[rhtPtr] > pivot && rhtPtr > beginning)
            rhtPtr = rhtPtr -1;
            
        if(rhtPtr > lftPtr)
            swap(arr, lftPtr, rhtPtr);
        else
            return lftPtr;
    }
}