STATUS_ACCESS_VIOLATION на 3-way quicksort (C++)

Question

Я попытался реализовать алгоритм 3-way quicksort на C++, описанный here. Неудача Я получаю исключение STATUS_ACCESS_VIOLATION.

template<typename T, size_t SIZE> 
void qsort(std::array<T, SIZE> &a, std::size_t lo, std::size_t hi) { 

    if (hi <= lo) { 
     return; 
    } 

    std::size_t lt = lo, gt = hi; 
    T v = a[lo]; 
    std::size_t i = lo; 

    while (i <= gt) { 
     if (a[i] < v) { 
      std::swap(a[lt++], a[i++]); 
     } else if (a[i] > v) { 
      std::swap(a[i], a[gt--]); 
     } else { 
      i++; 
     } 
    } 

    qsort(a, lo, lt - 1); 
    qsort(a, gt + 1, hi); 
} 

template<typename T, size_t SIZE> 
void quickSortThreeWay(std::array<T, SIZE> &a) { 
    std::size_t arraySize = sizeof(a)/sizeof(a[0]); 
    qsort(a, 0, arraySize - 1); 
} 

Массив - это std :: array, заполненный случайными значениями. Это отлично работает с другими алгоритмами.

Помогите найти проблему? Благодарю.

спасибо.

Answer 1

В этой строке кода:

qsort(a, lo, lt - 1); 

При ло равно 0, л может быть -1. К сожалению, ваша подпись не позволяет отрицательные числа, потому что вы используете size_t, так что в моем тесте, когда вот это 0, л - 1 является 18446744073709551615. то этот тест не делать то, что вы хотите:

if (hi <= lo) { return } 

Тогда он слепо продолжается и падает. Вы могли бы подумать, чтобы отрицательные числа в вашей подписи методы вместо size_t, например:

void qsort(std::array<T, SIZE> &a, int lo, int hi) { 
    std::cout << "qsort (a, " << lo << ", " << hi << ")" << std::endl; 

Когда я запускаю выше модифицированную подпись против массива из трех строк:

std::array<std::string, 3> a; 
a[0] = "hello"; 
a[1] = "abacus"; 
a[2] = "goodbye"; 
quickSortThreeWay (a); 

я получаю -1 для последний параметр:

qsort (a, 0, 2) 
qsort (a, 0, 1) 
qsort (a, 0, -1) 
qsort (a, 1, 1) 
qsort (a, 3, 2)