Why is my quicksort not working properly?

Question

I am working on sorting an array of objects in multiple ways. The objects are for areas, and I will be sorting data for those areas (more specifically population, concentration of water contaminants, and whether the area violates legal or health based water limits. My sorting results are almost accurate, and they are only off 5 spots out of 100.

t is a one character string that contains a keycode for how to sort the areas. For example, if t <-- "p", then it would test for population between two areas and return true or false.

Beforehand,

        statusL <-- True  statusH <-- True   high <-- length

Code:

Function partition(a() As Area, High As Long, Low As Long, t As String, progress As Boolean)
    Dim pivot As Area
    Dim i As Long, j As Long
    Set pivot = a(High)
    i = Low - 1
    j = Low
    For j = Low To High - 1
        If testAreas(a(j), pivot, t) Then
            i = i + 1
            Call swap(a(), i, j)
        End If
    Next j
    Call swap(a(), i + 1, High)
    If progress Then
        partition = i - 1
    Else
        partition = i + 1
    End If
End Function

Function QuickSort(a() As Area, High As Long, Low As Long, t As String, statusH As Boolean, statusL As Boolean, rounds As Long, oldPivot As Long, progress As Boolean)
    Dim pivot As Long
    If Low < High Then
        pivot = partition(a(), High, Low, t, progress)
        If rounds = 0 Then
            oldPivot = pivot
        End If
        rounds = rounds + 1
        If statusH = True Then
            If pivot >= High - 1 Then
                statusH = False
            End If
            Call QuickSort(a(), High, pivot - 1, t, statusH, statusL, rounds, oldPivot, progress)
        End If
        ''''''''''''''''
        If progress = False Then
            pivot = oldPivot
        End If
        progress = True
        ''''''''''''''''
        If statusL = True Then
            If pivot <= 1 Then
                statusL = False
            End If
            Call QuickSort(a(), pivot + 1, 0, t, statusH, statusL, rounds, oldPivot, progress)
        End If
    End If
End Function

Function swap(a() As Area, index1 As Long, index2 As Long)
    Dim x As Area
    Set x = a(index1)
    Set a(index1) = a(index2)
    Set a(index2) = x
End Function


Function testAreas(a As Area, b As Area, t As String)
    testAreas = False
    If t = "m" Then
        If a.max <= b.max Then
            testAreas = True
        End If
    End If
    If t = "p" Then
        Dim p1 As Double, p2 As Double
        p1 = a.pop
        p2 = b.pop
        If p1 <= p2 Then
            testAreas = True
        End If
    End If
    If t = "l" Then
        Dim L1 As Long, L2 As Long
        L1 = a.ll
        L2 = b.ll
        If L1 <= L2 Then
            testAreas = True
        End If
    End If
    If t = "h" Then
        Dim h1 As Long, h2 As Long
        h1 = a.hbl
        h2 = b.hbl
        If h1 <= h2 Then
            testAreas = True
        End If
    End If
    If t = "s" Then
        If a.state <= b.state Then
            testAreas = True
        End If
    End If
End Function

The order I am getting looks like this:

221351,30948,20602,12300,11702,8980,2342,2300,1395,1475,1005,993,852,775,935, 904,975,654,650,600,794,650,740,493,795

...and as this goes down, it gets increasingly inaccurate then close to the end it becomes more accurate.

Answer 1

I don't understand the need for the progress parameter. For quicksort, if the pivot swap is using i+1, then the partition function should be returning i+1. To avoid stack overflow, use recursion on the smaller part, then loop back for the larger part. Example C++ code using Lomuto partition scheme:

void QuickSort(uint64_t a[], int lo, int hi)
{
    while (lo < hi){
        uint64_t p = a[hi];
        int i = lo;
        for (int j = lo; j < hi; ++j){
            if (a[j] < p){
                std::swap(a[j], a[i]);
                ++i;
            }
        }
        std::swap(a[i], a[hi]);
        if(i - lo <= hi - i){
            QuickSort(a, lo, i-1);
            lo = i+1;
        } else {
            QuickSort(a, i+1, hi);
            hi = i-1;
        }
    }
}