HiveBrain v1.2.0
Get Started
← Back to all entries
snippetjavaMinor

Potential quicksort optimizations

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
sortingcodereviewjavastackoverflowquick-sort
potentialoptimizationsquicksort

Problem

I implemented qsort() like this. I was wondering what improvements I could do to make it better.

public static void qsort(int[] a, int start, int end) {
    if (start >= end) return;
    int pivot = start;
    int lt = start + 1;
    int gt = end;
    int temp;
    while (lt  a[lt]) {
            temp = a[pivot];
            a[pivot] = a[lt];
            a[lt] = temp;
            pivot = lt++;
        } else {
            while (gt >= lt)  {
                if (a[gt] < a[lt]) {
                    temp = a[lt];
                    a[lt] = a[gt];
                    a[gt] = temp;
                    break;
                }
                gt--;
            }
            gt--;
        }
    }
    qsort(a, start, pivot - 1);
    qsort(a, pivot + 1, end);
}

Solution

One thing I quickly spot is this:

If your second while loop completes naturally instead of via a break, you will also exit the first while loop. Thus the last instruction executed, gt--, is unnecessary.

Let's look at the execution paths:

//BEGINLOOPS
while (lt  a[lt]) {
        temp = a[pivot];
        a[pivot] = a[lt];
        a[lt] = temp;
        pivot = lt++;
    } else {
        while (gt >= lt)  {//If false, does gt--;, then jumps to ENDLOOPS
            if (a[gt] < a[lt]) {
                temp = a[lt];
                a[lt] = a[gt];
                a[gt] = temp;
                break;//does gt--;, then jumps to BEGINLOOPS
            }
            gt--;
        }
        gt--;
    }
}
//ENDLOOPS
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);


There's only 2 ways the second while loop can end. Either via a break or via gt decrementing until it equalizes with lt.

So we should alter the one execution path where the gt--; is unnecessary.

//BEGINLOOPS
while (lt  a[lt]) {
        temp = a[pivot];
        a[pivot] = a[lt];
        a[lt] = temp;
        pivot = lt++;
    } else {
        while (gt >= lt)  {//If false, jumps to ENDLOOPS
            if (a[gt] < a[lt]) {
                temp = a[lt];
                a[lt] = a[gt];
                a[gt] = temp;
                gt--;//does gt--;,
                break;//then jumps to BEGINLOOPS
            }
            gt--;
        }
    }
}
//ENDLOOPS
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);


That saves you one instruction for each time you end via that one execution path.

Additionally, you know what pivot is already, so I'd split this in a helper function and a recursive function.

public static void quickSort(int[] a, int start, int end) {
    if (start >= end) return;
    qsort(a, start, end);
}

private static void qsort(int[] a, int start, int end) {
    int pivot = start;
    int lt = start + 1;
    int gt = end;
    int temp;
    while (lt  a[lt]) {
            temp = a[pivot];
            a[pivot] = a[lt];
            a[lt] = temp;
            pivot = lt++;
        } else {
            while (gt >= lt)  {
                if (a[gt] < a[lt]) {
                    temp = a[lt];
                    a[lt] = a[gt];
                    a[gt] = temp;
                    gt--;
                    break;
                }
                gt--;
            }
        }
    }
    pivot--;
    if(start < pivot){
        qsort(a, start, pivot);
    }
    if(lt < end){
        qsort(a, lt, end);
    }
}


Whoa, that's different near the end. Yeah, I rushed ahead. Let me explain.

pivot starts at start. lt starts at start + 1, which is pivot + 1. Furthermore, there's only one place where pivot is changed (pivot = lt++) and there's only one place where lt is changed (also pivot = lt++). Looking at that line tells us it does this:

Set pivot to the value of lt (which by definition is pivot + 1), then up lt by one, making lt to be pivot + 1 again. One wonders whether you even need the different variable - if you wanted to conserve memory, I would strip the unneeded variable.

So with that logic, excepting the moment of which that one line is executed in which they are altered, pivot and lt are always 1 apart. Thus I can use lt as a shorthand for pivot + 1.

Examples, with pivot = 12:

qsort(a, start, pivot - 1);//12 - 1 = 11
qsort(a, pivot + 1, end);//12 + 1 = 13

    pivot--;//lt is still 13, 12-- = 11
    if(start = end is false, so only run if start < end is true.
        qsort(a, start, pivot);//11
    }
    if(lt < end){//only run if start < end is true.
        qsort(a, lt, end);//lt is still 13, I changed nothing to it.
    }


You should also consider removing the pivot variable and seeing if that makes a difference.

That said, all performance optimizations should be profiled and benchmarked properly. Who knows what optimizations the JVM will make for you. But if you were a human who executed the code by hand, these optimizations would speed the code up for you.

Looking deeper at it (why not?) shows me one more problem: if you made no swaps, you will still split around your pivot, reiterating the entire array except one element. That's really, really bad. You'll basically have \$T_{end-start}\$ iterations, where \$T\$ is a triangular number. In other words: 100 elements sorted gives you 5050 iterations or so. That's bad.

Let's add a boolean for that.

```
public static void quickSort(int[] a, int start, int end) {
if (start >= end) return;
qsort(a, start, end);
}

private static void qsort(int[] a, int start, int end) {
int pivot = start;
int lt = start + 1;
int gt = end;
int temp;
boolean swapped = false;
while (lt a[lt]) {
temp = a[pivot];
a[pivot] = a[lt];
a[lt] = temp;
pivot = lt++;
swapped = true;
} else {
while (gt >= lt) {

Code Snippets

//BEGINLOOPS
while (lt <= gt) {
    if (a[pivot] > a[lt]) {
        temp = a[pivot];
        a[pivot] = a[lt];
        a[lt] = temp;
        pivot = lt++;
    } else {
        while (gt >= lt)  {//If false, does gt--;, then jumps to ENDLOOPS
            if (a[gt] < a[lt]) {
                temp = a[lt];
                a[lt] = a[gt];
                a[gt] = temp;
                break;//does gt--;, then jumps to BEGINLOOPS
            }
            gt--;
        }
        gt--;
    }
}
//ENDLOOPS
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);
//BEGINLOOPS
while (lt <= gt) {
    if (a[pivot] > a[lt]) {
        temp = a[pivot];
        a[pivot] = a[lt];
        a[lt] = temp;
        pivot = lt++;
    } else {
        while (gt >= lt)  {//If false, jumps to ENDLOOPS
            if (a[gt] < a[lt]) {
                temp = a[lt];
                a[lt] = a[gt];
                a[gt] = temp;
                gt--;//does gt--;,
                break;//then jumps to BEGINLOOPS
            }
            gt--;
        }
    }
}
//ENDLOOPS
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);
public static void quickSort(int[] a, int start, int end) {
    if (start >= end) return;
    qsort(a, start, end);
}


private static void qsort(int[] a, int start, int end) {
    int pivot = start;
    int lt = start + 1;
    int gt = end;
    int temp;
    while (lt <= gt) {
        if (a[pivot] > a[lt]) {
            temp = a[pivot];
            a[pivot] = a[lt];
            a[lt] = temp;
            pivot = lt++;
        } else {
            while (gt >= lt)  {
                if (a[gt] < a[lt]) {
                    temp = a[lt];
                    a[lt] = a[gt];
                    a[gt] = temp;
                    gt--;
                    break;
                }
                gt--;
            }
        }
    }
    pivot--;
    if(start < pivot){
        qsort(a, start, pivot);
    }
    if(lt < end){
        qsort(a, lt, end);
    }
}
qsort(a, start, pivot - 1);//12 - 1 = 11
qsort(a, pivot + 1, end);//12 + 1 = 13

    pivot--;//lt is still 13, 12-- = 11
    if(start < pivot){//only run if start >= end is false, so only run if start < end is true.
        qsort(a, start, pivot);//11
    }
    if(lt < end){//only run if start < end is true.
        qsort(a, lt, end);//lt is still 13, I changed nothing to it.
    }
public static void quickSort(int[] a, int start, int end) {
    if (start >= end) return;
    qsort(a, start, end);
}


private static void qsort(int[] a, int start, int end) {
    int pivot = start;
    int lt = start + 1;
    int gt = end;
    int temp;
    boolean swapped = false;
    while (lt <= gt) {
        if (a[pivot] > a[lt]) {
            temp = a[pivot];
            a[pivot] = a[lt];
            a[lt] = temp;
            pivot = lt++;
            swapped = true;
        } else {
            while (gt >= lt)  {
                if (a[gt] < a[lt]) {
                    temp = a[lt];
                    a[lt] = a[gt];
                    a[gt] = temp;
                    swapped = true;
                    gt--;
                    break;
                }
                gt--;
            }
        }
    }
    if(swapped){
        pivot--;
        if(start < pivot){
            qsort(a, start, pivot);
        }
        if(lt < end){
            qsort(a, lt, end);
        }
    }
}

Context

StackExchange Code Review Q#58477, answer score: 3

Revisions (0)

No revisions yet.