4
\$\begingroup\$

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 <= 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;
                    break;
                }
                gt--;
            }
            gt--;
        }
    }
    qsort(a, start, pivot - 1);
    qsort(a, pivot + 1, end);
}
\$\endgroup\$
3
\$\begingroup\$

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 <= 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);

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 <= 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);

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 <= 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);
    }
}

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 < 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.
    }

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 <= 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);
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.