1

文字列の配列をソートするためのクイックソートアルゴリズムを書いています。

問題は、配列とそのすべてをそこに出力するため、左右のクイックソート配列を割り当てた直後に、データを含む配列が何かで上書きされているように見えることですが、malloc を使用して他の配列を割り当てた後、それを印刷します。繰り返しますが、いくつかの要素が欠けています。

出力は次のとおりです。

Pivot: 2
Emma, Olivia, Victoria, Gwyneth, Chloe, Hayley, Scarlett,
Emma, Olivia, Victoria, Gwyneth, , , ,

誰が何が起こっているか知っていますか？何が欠けていますか？

char **concatenate(char **array1, int n1, char *pivot, char **array2, int n2, int len){
int i=0, j=0;
int elements = n1 + n2 + 1;

// alocating array
char **concat = (char**) malloc(sizeof(*concat) * elements);
concat[0] = (char*) malloc(sizeof(*concat) * elements * len);
for(i=1; i<elements; i++)
    concat[i] = &(concat[0][i*len]);

// concatenating 
for(i=0; i<n1; i++)
    concat[i] = array1[i];
concat[i++] = pivot;
for(j=0; j<n2; j++)
    concat[i++] = array2[j];

// returning
return concat;
}

char **quicksort(char **array, int elements, int len){
// array is already sorted
if(elements < 2)
    return array;

int pivot;
int i=0, l=0, r=0;

// selecting the pivot (median)
if(elements % 2 == 0)
    pivot = ((elements + 1) / 2) -1;
else
    pivot = (elements / 2) -1;

//REMOVE
printf("Pivot: %d\n", pivot);
for(i=0; i<elements; i++)
    printf("%s, ", array[i]);
printf("\n");

// alocating arrays
char **left = (char**) malloc(sizeof(*left) * pivot);
left[0] = (char*) malloc(sizeof(*left) * pivot * len);
for(i=1; i<pivot; i++)
    left[i] = &(left[0][i*len]);

char **rigth = (char**) malloc(sizeof(*rigth) * pivot);
rigth[0] = (char*) malloc(sizeof(*rigth) * pivot * len);
for(i=1; i<pivot; i++)
    rigth[i] = &(rigth[0][i*len]);

//REMOVE
for(i=0; i<elements; i++)
    printf("%s, ", array[i]);
printf("\n");

//quicksorting
for(i=0; i<elements; i++){
    if(array[i] == array[pivot])
        continue;

    int comp = strcmp(array[i], array[pivot]);

    //REMOVE
    printf("%d: strcmp %s, %s is %d\n", i, array[i], array[pivot], comp);

    if(comp < pivot)
        left[l++] = array[i];
    else
        rigth[r++] = array[i];
}

//REMOVE
printf("concatenate(");
for(i=0; i<l; i++)
    printf("%s ", left[i]);
printf("|%s| ", array[pivot]);
for(i=0; i<r; i++)
    printf("%s ", rigth[i]);
printf(")\n");

// recursion and return
return concatenate(quicksort(left, l, len), l, array[pivot], quicksort(rigth, r, len), r, len);
}

int main(int argc, char *argv[]){
int i, j, aux;                  

char **teste = (char**) malloc(sizeof(*teste) * 7);
teste[0] = (char*) malloc(sizeof(*teste) * 7 * 128);
for(i=1; i<7; i++)
    teste[i] = &(teste[0][i*128]);
teste[0] = "Emma";
teste[1] = "Olivia";
teste[2] = "Victoria";
teste[3] = "Gwyneth";
teste[4] = "Chloe";
teste[5] = "Hayley";
teste[6] = "Scarlett";

quicksort(teste, 7, 128);

printf("AFTER\n");
for(i=0; i<7; i++)
    printf("%s, ", teste[i]);
printf("\n");

return 0;
}
4

1 に答える 1

8

クイックソートに割り当てる理由はありません。実際、関数は、サブシーケンスの呼び出しにポインター演算を使用して、クイックソート(char *arr[], unsigned int len) の単純なインターフェイスで簡単に十分です。

ポインタを交換するためのスワップ アルゴリズムを提供します。

void swap_str_ptrs(char const **arg1, char const **arg2)
{
    const char *tmp = *arg1;
    *arg1 = *arg2;
    *arg2 = tmp;
}

次に、アルゴリズムは次のとおりです。

void quicksort_strs(char const *args[], unsigned int len)
{
    unsigned int i, pvt=0;

    if (len <= 1)
        return;

    // swap a randomly selected value to the last node
    swap_str_ptrs(args+((unsigned int)rand() % len), args+len-1);

    // reset the pivot index to zero, then scan
    for (i=0;i<len-1;++i)
    {
        if (strcmp(args[i], args[len-1]) < 0)
            swap_str_ptrs(args+i, args+pvt++);
    }

    // move the pivot value into its place
    swap_str_ptrs(args+pvt, args+len-1);

    // and invoke on the subsequences. does NOT include the pivot-slot
    quicksort_strs(args, pvt++);
    quicksort_strs(args+pvt, len - pvt);
}

それがすべてです。分割も含めて。

使い方

2 つの一般的な再帰的クイックソート アルゴリズムがあります:スクイーズとスイープです。これがスイープアルゴリズムです。シーケンスを上に移動し、ピボット値 (ループが開始する前にシーケンスの最後にスワップされる) よりも「小さい」要素をターゲット スロットにスワップします。そのインデックスは最初はシーケンスの先頭であり、それに応じて増加します。各スワップ操作。「スイープ」が終了すると、そのスロットの下にあるものはすべてその値よりも「小さい」ため、pvtインデックスはピボット値が属する場所になります。そのため、ピボット値を所定の位置に配置するために、もう 1 つのスワップが行われます。その後、再帰される 2 つのパーティションがあります。これらのパーティションのいずれにも含まれません。それは、私たちが知っている唯一の価値であり、最終的な安息の場所にあります。

テストハーネス

上記のコードを含めて、意図的に順不同の基本的な文字列セットでこれをテストします。

void print_list(char const *args[], unsigned len)
{
    unsigned i=0;
    for (;i<len;++i)
        puts(args[i]);
}

int main()
{
    char const *args[] =
    {
        "this", "is", "a", "test", "of", "quicksort", "with", "strings"
    };

    srand((unsigned)time(NULL));
    quicksort_strs(args, sizeof(args)/sizeof(*args));
    print_list(args, sizeof(args)/sizeof(*args));
    return 0;
}

出力

a
is
of
quicksort
strings
test
this
with

非再帰的な実装

上記のアルゴリズムは、非再帰的な実装に非常に適していることに注意してください。ローカル動的スタックは、データのペア (ポインターと長さ) を保持するために使用されます。単純なセグメント (長さ 1 または 0 のセグメント) をスタックにプッシュしないように最適化されています。ある実装では次のようにします。

void quicksort_strs(char const *args[], unsigned int len)
{
    // holds our non-recursive stack of segments
    struct segment
    {
        char const **arr;
        unsigned int len;
        struct segment* next;
    } *stack = NULL;

    stack = malloc(sizeof(*stack));
    stack->arr = args;
    stack->len = len;
    stack->next = NULL;

    while (stack != NULL)
    {
        unsigned int i, pvt=0;
        struct segment *tmp = stack;
        stack = stack->next;

        // pull values and delete segment record
        args = tmp->arr;
        len = tmp->len;
        free(tmp);

        // nothing to unary segments
        if (len <= 1)
            continue;

        // swap a randomly selected value to the last node
        swap_str_ptrs(args+((unsigned int)rand() % len), args+len-1);

        // reset the pivot index to zero, then scan
        for (i=0;i<len-1;++i)
        {
            if (strcmp(args[i], args[len-1]) < 0)
                swap_str_ptrs(args+i, args+pvt++);
        }

        // move the pivot value into its place
        swap_str_ptrs(args+pvt, args+len-1);

        // lhs segment push
        if (pvt > 1)
        {
            tmp = malloc(sizeof(*tmp));
            tmp->arr = args;
            tmp->len = pvt;
            tmp->next = stack;
            stack = tmp;
        }

        // rhs segment push
        if ((len - ++pvt) > 1)
        {
            tmp = malloc(sizeof(*tmp));
            tmp->arr = args+pvt;
            tmp->len = len-pvt;
            tmp->next = stack;
            stack = tmp;
        }
    }
}

既製のノード スタック実装を使用すると、これを大幅に短縮できることは明らかですが、アイデアはすぐに明らかになるはずです。「スタック」の先頭ではなく末尾realloc()にノードを保持するためのスキーマも同様に興味深いものです。ポインタ管理の必要がなくなり、代わりにインデックスに置き換えられるからです。nexttop

とにかく、頑張ってください。お役に立てば幸いです。

于 2013-10-27T02:18:35.320 に答える