Почему моя быстрая сортировка не работает должным образом?

Question

Я работаю над сортировкой массива объектов несколькими способами.Объекты предназначены для областей, и я буду сортировать данные для этих областей (более конкретно, численность населения, концентрацию загрязнителей воды и то, нарушает ли область законные или основанные на здоровье пределы воды. Мои результаты сортировки почти точны, и они только не соответствуют 5пятна из 100.

t - это строка из одного символа, которая содержит ключевой код для сортировки областей. Например, если t <- "p", то это будет проверка на заполненностьмежду двумя областями и верните true или false. </p>

Заранее,

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

Код:

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

Порядок, который я получаю, выглядит следующим образом:

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

... и, как это происходит, становитсястановится все более неточным, а ближе к концу становится более точным.

Answer 1

Я не понимаю необходимости параметра progress. Для быстрой сортировки, если в сводном свопе используется i+1, функция разделения должна возвращать i+1. Чтобы избежать переполнения стека, используйте рекурсию для меньшей части, а затем вернитесь назад для большей части. Пример кода C ++ с использованием схемы разбиения Lomuto:

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