пример bsort из программирования жемчуг

Question

В Programming Pearls есть алгоритм, который сортирует массивы различной длины, но сортирует по времени, пропорциональному сумме их длины. Например, если у нас есть массив записей x[0...n-1], и каждая запись имеет целочисленную длину и указатель на массив bit[0...length-1].

Код реализован следующим образом:

void bsort(l, u, depth){
    if (l >= u)
        return ;
    for (i = l; i <= u; i++){
        if (x[i].length < depth)
            swap(i, l++);
    }
    m = l;
    for (int i = l; i < u; i++){
        if (x[i].bit[depth] == 0)
            swap(i, m++);
    }
    bsort(l, m - 1, depth + 1);
    bsort(m, u, depth + 1);
}

Мой вопрос таков, учитывая запись:

x[6] = {"car", "bus", "snow", "earth", "dog", "mouse"}

Я знаю, как получить длину строки, но как насчет битового массива? Как я могу сделать битовый массив, подходящий для этого массива строк? И даже x[i].bit[depth] как я могу это реализовать?

Answer 1

Массивы символов (или любого другого типа в этом отношении) также являются массивами битов - в конце концов, символы состоят из битов.Таким образом, вам не нужно создавать отдельный массив, вам просто нужно найти способ доступа к данному биту в массиве.Для этого вам придется использовать некоторые битовые манипуляции.Вы можете найти несколько примеров того, как это можно сделать здесь: Есть ли какой-нибудь более умный способ извлечь из массива битов? .

Как правило, сначала вы должны выяснить байт требуемого бита.в, а затем получить значение этого конкретного бита.Что-то вроде:

char* array = "the array";
int required_bit = 13;
int bit = required_bit & 0x7;  // get the bit's offset in its byte
int byte = required_bit >> 3;  // get the bit's byte
int val = (array[byte] >> bit) & 0x1; // check if the bit is 1

Теперь оберните это в функцию (возможно, с дополнительными проверками границ, чтобы убедиться, что данный required_bit не находится вне массива), и используйте с x[i].