Отладка по индексируемому массиву быстрой сортировки

Question

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

Учитывая индекс массива смежных, упорядоченные числа (представляющие элементы в массиве данных), вам все равно придется сравнить значения данных; ты только получить доступ к ним через индекс. Вы меняете значения индекса, однако, не значения данных.

Unsorted data: 09 04 47 05 03 12
Index array:   00 01 02 03 04 05

After sort,
Unsorted data: 09 04 47 05 03 12
Index array:   04 01 03 00 05 02

Print the values indexed by the index array,
from beginning to end of the array:

Index array [0] value [04] data array [04] = 03
            [1]        01             [01]   04
            [2]        03             [03]   05
            [3]        00             [00]   09
            [4]        05             [05]   12
            [5]        02             [02]   47

Output is the data, ordered at the output

Я добавляю только одну вещь. Компаратор является обычным компаратором, за исключением того, что если мы сравниваем два разных символа с одинаковыми значениями, мы сравниваем следующий символ каждого и возвращаем этот результат. То есть, сравнивая повороты.

int compare(unsigned char i, unsigned char j);

Я не буду публиковать определение, потому что я уверен, что оно работает идеально. Ошибка заключается в определении быстрой сортировки.

void quicksort(unsigned char* a, unsigned char left, unsigned char right) {
    unsigned char i = left;
    unsigned char j = right;
    unsigned char half = (left + right) / 2;
    while (i <= j) {
        while ((compare(a[i], a[half]) == -1) && (i < right))
            i++;
        while ((compare(a[j], a[half]) == 1) && (j > left))
            j--;

        if (i <= j) {
            unsigned char aux = a[i];
            a[i] = a[j];
            a[j] = aux;
            i++;       //THERE
            j--;       //THERE
        }

    }

    if (left < j)
        quicksort(a, left, j);
    if (i < right)
        quicksort(a, i, right);

}

Иногда i = 255 и j = 0, и я не знаю почему, программа попадает туда, и их значения переполняются. Я искал ошибки тысячу раз и не могу найти, где в этом ошибка.
Заметки: 1) Я прекрасно осведомлен о C ++ беззнаковых диапазонах символов и не могу изменить их на int. 2) Я фактически не включаю объявление фактического массива данных. Функция сравнения имеет к нему доступ, поскольку является атрибутом своего класса.

Answer 1

Э-э, вы не можете хранить числа больше 255 или меньше 0 в неподписанном символе.Символ без знака может хранить диапазон, определенный одним байтом без знака, таким образом, 8 двоичных цифр.2 ^ 8 = 256, и так как мы включаем 0, мы имеем 256 - 1, что дает нам 255. (или в шестнадцатеричном, 0xFF)

Попробуйте использовать целые числа или даже шорты.(ключевое слово short)