0

ソートのカウントに問題があります。テーブルを並べ替えるときは、機能することもありますが、機能しないこともあり（k == sizeの場合は機能しません）、理由がわかりません。助けてください。これは私のコードです：

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 100000
int tabA[MAX];
int tabB[MAX];
int tabC[MAX];
int k;

void scope(int size){
int i, max = 0, min;

min = tabA[1];

    for(i = 1; i <= size; i++){
        if(tabA[i] > max)
            max = tabA[i];
        if(tabA[i] < min)
            min = tabA[i];
    }

    k = max - min + 1;
}

void rand1(int size){
    int i;
    srand(time(NULL));

    for(i = 0; i <= size; i++)
        tabA[i] = rand() % 8;
} 

void countingsort(int size){
    int i;

    for(i = 0; i < k; i++)
        tabC[i] = 0;

    for(i = 0; i < size; i++)
        tabC[tabA[i + 1]] = tabC[tabA[i + 1]] + 1;

    for(i = 1; i <= k; i++)
        tabC[i] = tabC[i] + tabC[i - 1];

    for(i = size; i >= 1; i--){
        tabB[tabC[tabA[i]]] = tabA[i];
        tabC[tabA[i]] = tabC[tabA[i]] - 1;
    }   
}

int main(void){
    int size, i;

    printf("Please write how many numbers you wont to sort: ");
    scanf("%d", &size);

    rand1(size);
    scope(size);
    countingsort(size);

    printf("Numbers to sort:\n");
    for(i = 1; i <= size; i++)
        printf("%d\n", tabA[i]);

    printf("\nK: %d\n\n", k);

    printf("Sorting numbers:\n");
    for(i = 1; i <= size; i++)
        printf("%d\n", tabB[i]);

    return 0;
}

すべての助けをありがとう。

4

1 に答える 1

1

少なくともこのコード：

for(i = 0; i < k; i++)
    tabC[i] = 0;

for(i = 0; i < size; i++)
    tabC[tabA[i + 1]] = tabC[tabA[i + 1]] + 1;

for(i = 1; i <= k; i++)
    tabC[i] = tabC[i] + tabC[i - 1];

最初の初期化ループでは が実行されますiが0..k-1、最後のループでは が初期化されていると仮定してiから実行されるという問題があります。また、中間ループは、値の範囲が であると想定していますが、そうではない可能性があります (ランダム化関数を見ると、実際にはそうである可能性がありますが、これは偶然の一致だと思います)。1..ktabCtabA0..k

于 2012-11-12T19:38:53.460 に答える