CODEWITHSUNDEEP
javasortingquicksort
Chris Dance
Chris Dance

Reputation: 3

Quicksort Algorithm won't complete in worst case

For a coursework assignment I have been tasked with implementing a basic Quicksort Algorithm. I have implemented what I thought to be a working Quicksort, however it doesn't work for one particular array that we have to test. This array is supposed to be a worst case and should understandably take more comparisons, but I simply cannot get it to produce a sorted array in this case.

Pseudo Code:

Begin quickSort

if (R > L) then

p := partition(A,L,R);

quickSort(A,L,p-1);

quickSort(A,p+1,R);

fi

End

Begin partition

v := A[right]

pL := left; pR := right-1;

while (pL < pR) do

while (A[pL] < v) do pL:=pL+1 od while (A[pR]>=v and pR>left) do

pR:=pR-1

od

if (pL < pR) then

swap(A,pL,pR)

fi

od

swap(A,pL,right);

return pL;

The code in question:

public void quickSort(int[] A, int L, int R) {
    if (L < R) {
        int p = partition(A, L, R);
        quickSort(A, L, p - 1);
        quickSort(A, p + 1, R);
    }
}
private int partition(int[] A, int left, int right) {
    int pivot = A[right];
    int pointerLeft = left;
    int pointerRight = right - 1;
    while (pointerLeft < pointerRight) {
        while (A[pointerLeft] < pivot) {
            pointerLeft = pointerLeft + 1;
            compQS++;
        }
        while (A[pointerRight] > pivot && pointerRight > left) {
            pointerRight = pointerRight - 1;
            compQS++;
        }
        if (pointerLeft < pointerRight) {
            swap(A, pointerLeft, pointerRight);
        }
    }
    swap(A, pointerLeft, right);
    return pointerLeft;

}

private void swap(int[] A, int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

The array in question:

1 3 41 5 6 9 11 20 21 22 23 24 26 28 29 30 33 39 41 41 43 45 46 2 54 55 55 56 57 60 61 63 65 66 67 69 69 70 71 180 73 74 76 77 79 138 81 83 85 88 91 92 92 94 94 95 99 101 101 103 105 106 107 110 113 115 118 125 127 128 129 136 80 143 144 147 148 150 152 153 155 156 158 163 169 170 171 175 176 178 75 184 185 189 190 193 194 195 196 199

Any guidance would be greatly appreciated. I can't help but think it's something to do with duplicates but can't see where my implementation is going wrong.

Upvotes: 0

Views: 161

Answers (2)

Waclock
Waclock

Reputation: 1726

I see two possible problems in your code:

1) When you first call quickSort you are missing the mid value (you use p-1 as your right expression for the first call, and p+1 as your left expression for the second call, what happens to p?)

2) You are swapping pointerLeft with right

Try this instead:

quicksort(A,L,p);
quicksort(A,p+1,R);

And

swap(A,pointerLeft,pointerRight);

Give it a try!

Upvotes: 0

PMF
PMF

Reputation: 17298

Looking at the code, two points seem fishy:

In the recursion, you write

   quickSort(A, L, p - 1);
   quickSort(A, p + 1, R);

either one should probably be p, otherwise you're missing the middle element.

The other line that seems odd is

swap(A, pointerLeft, right);

I think this will cause trouble if right (which is the pivot) is the largest value between left and right. Thinking about it, I think the problem is in your partition code when the pivot is an extreme value (smallest or largest in the set). This would coincide with the statement that the given array was a very bad case.

Upvotes: 1

Related Questions