動的メモリ割り当てとsize_t型を使用したカウンティングソートの実装

まず、カウンティングソートのアルゴリズムについて簡単に説明します。このアルゴリズムでは、ソートされる整数の範囲を事前に知っている必要があります。例えば、0から最大値までの範囲がわかっている場合、その範囲の要素数分の配列を用意します。この配列は、各整数の出現回数をカウントするために使用されます。

次に、ソート対象の配列を走査し、各整数の出現回数をカウントします。これは、カウンティング配列の対応するインデックスに対してインクリメントすることで行います。

その後、カウンティング配列を累積和に変換します。これは、各要素をその前の要素と加算することで行います。これにより、各整数の最終的なソート位置が決定されます。

最後に、元の配列を走査し、各整数をカウンティング配列を参照して適切な位置に配置します。

以下に、動的メモリ割り当てとsize_t型を使用したカウンティングソートのコード例を示します。

#include <stdio.h>
#include <stdlib.h>
void countingSort(int* array, int size) {
    int max = array[0];
    for (int i = 1; i < size; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    size_t countSize = (max + 1) * sizeof(int);
    int* count = (int*)malloc(countSize);
    if (count == NULL) {
        printf("メモリ割り当てエラー\n");
        return;
    }
    for (int i = 0; i < size; i++) {
        count[array[i]]++;
    }
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }
    int* sorted = (int*)malloc(size * sizeof(int));
    if (sorted == NULL) {
        printf("メモリ割り当てエラー\n");
        free(count);
        return;
    }
    for (int i = size - 1; i >= 0; i--) {
        sorted[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }
    for (int i = 0; i < size; i++) {
        array[i] = sorted[i];
    }
    free(count);
    free(sorted);
}
int main() {
    int array[] = {4, 2, 2, 8, 3, 3, 1};
    int size = sizeof(array) / sizeof(array[0]);
    countingSort(array, size);
    printf("ソート結果: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、count配列とsorted配列を動的に割り当てています。count配列はカウンティング配列として使用され、sorted配列はソートされた結果を格納するために使用されます。

上記のコードを実行すると、次のような出力が得られます:

ソート結果: 1 2 2 3 3 4 8

以上が、動的メモリ割り当てとsize_t型を使用したカウンティングソートの実装方法です。この方法を使えば、大きな範囲の整数を効率的にソートすることができます。