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

В 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] как мне это реализовать?


c++ sorting programming-pearls
person dato datuashvili    schedule 15.10.2011    source источник
comment
Я пытался очистить это, но ваш вопрос все еще не очень ясен. Это в основном то, что вы думаете о сортировке char[] и хотите знать, можете ли вы отсортировать битовый массив? Я думаю, это зависит от того, как реализован ваш битовый массив.   -  person Brendan Long    schedule 15.10.2011
comment
хочу сказать что мне тоже не понятно как реализовать битовую сортировку со строковой записью, не могу понять   -  person dato datuashvili    schedule 15.10.2011

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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].

person eran    schedule 15.10.2011
comment
это очень отличный ответ @eran, только один вопрос предположим, что вместо строкового массива у нас есть целочисленный массив, тогда x[i].length это число цифр для представления этого числа да? и дополнительно x[i].bit[depth ] это бит в числе на глубине позиции да? - person dato datuashvili; 15.10.2011
comment
Вы не можете использовать x[i].length для получения длины массива, это не Java... Со строками вы можете использовать strlen. С целыми числами вы должны передать размер вместе с массивом. Кроме того, у вас нет части bit[depth] — вы работаете над частью x[i]. Наконец, если у вас есть массив int, вам придется внести некоторые изменения — целые числа не являются 1 байтом, поэтому array[byte] не будет обращаться к byte байту, но byte int. проще всего было бы преобразовать int* в char*. - person eran; 15.10.2011
comment
извините @eran, но я уже запутался, в моем примере, как будет написан мой код? у меня есть массив строк, показанный в примере, скажите, пожалуйста, как будет выглядеть мой код? - person dato datuashvili; 15.10.2011
comment
Сначала вы должны, скажем, создать функцию int get_bit(char* array, int bitpos). Затем назовите его как int bit_val = get_bit(x[i], depth) (при условии, что depth — это бит, значение которого вас интересует). Это даст вам бит depth в массиве x[i]. - person eran; 15.10.2011
comment
но x[i] - это массив символов, а не один символ да? или это не имеет значения - person dato datuashvili; 15.10.2011
comment
Это должен быть массив символов. Посмотрите на определение функции и пример кода. - person eran; 15.10.2011
comment
хорошо @eran спасибо за помощь, я попытаюсь понять это, только одна путаница в том, что даже я верну свой пример, мы должны взять массив x, который содержит строки, и эти строки сами по себе являются массивом символов, так что адский код из жемчуга программирования - person dato datuashvili; 15.10.2011