バケットソート（ビンソート）の解説（C言語サンプルプログラム付き）

このページにはプロモーションが含まれています

このページでは、ソートアルゴリズムの１つである「バケットソート（別名：ビンソート）」について解説を行い、その後バケットソートを行うC言語のサンプルプログラムの紹介をしていきたいと思います。

Contents

バケットソートとは
- バケットソートの考え方
バケットソートのプログラム
バケットソートの特徴
まとめ

バケットソートとは

では、バケットソートがどのようなソートアルゴリズムであるかについて解説していきます。

バケットソートの考え方

バケットソートは、バケツにデータを入れる＆バケツからデータを取り出すことでソートするソートアルゴリズムになります（別にバケツでなくても入れ物であれば良いです。このページではバケツを例に解説しています）。

バケットソートでは、まずソートするデータが取りうる値分（もしくはそれ以上）のバケツを用意します。

バケツには、前述のソートするデータが取りうる値のラベルが貼られているとします。

続いて、ソートするデータ全てをバケツに入れていきます。この時、各データは、そのデータの値のラベルが貼られたバケツに入れるようにします。

全てのデータを入れ終わったら、次は貼られたラベルの値が小さなバケツから順にデータを取り出していきます。

各バケツにはラベルの値と同じ値を持つデータが入っているので、ラベルの値が小さいバケツから順にデータを取り出して並べれば、元々の集合のデータが自然と昇順に並ぶことになります。

逆にラベルの値が “大きい” バケツから順にデータを取り出して並べれば、降順にソートされることになります。

ここではバケツにラベルを貼り付ける例で解説しましたが、要は “各バケツにどの値のデータが入っているかを管理” し、その “値の小さいバケツから順にデータの取り出し” を行うようにしていれば良いです。

バケットソートでソートを行う考え方の解説は以上になります。ただかなり抽象的な解説になっているので、続いて実際のソースコードを確認しながら具体的な解説をしていきたいと思います。

バケットソートのプログラム

このバケットソートを実装する上でポイントになるのは、”どうやってバケツを実現するかどうか” の点になると思います。

バケットソートにおいては、このバケツの実現方法によってさまざまな実装が存在します。ここでは下記の３つのバケツの実現方法での実装の考え方と、実際に実装を行なったバケットソートの関数を紹介していきたいと思います。

単純に配列の各要素をバケツとする
データの分布を考慮してバケツを準備する
データを入れるときにバケツを動的に追加する

1. に関しては、”データの重複がある時” にはソートがうまく行えない方法になります。が、シンプルに実装できますので、バケットソートを直感的に理解する上ではオススメの実装方法になります。

2. と 3. に関しては “データの重複がある時” にでもソートがうまく行えるので実用性の高い実装方法になります。が、1. に比べると若干実装が難しいと思います。

ではここからは、これらのバケツの実現方法別に、実装の考え方と実際のプログラムの紹介をしていきたいと思います。

単純に配列の各要素をバケツとする

まずは、単純に配列の各要素をバケツとしてバケットソートを行う方法を解説していきます。

実装の考え方

この方法では、配列の各要素を１つのバケツとしてソートを行います。

配列の各要素は、”添字” と一致する値を持つデータを入れるためのバケツとして扱います。つまり、配列名を buckets とした時、buckets[x] には値が x のデータを格納します。

全てのデータを buckets に格納した後は、buckets の先頭から順にデータを取り出します。以上でソートの処理は完了です。

非常に簡単ですが、これでも “データの重複がない” 場合はバケツとしてしっかり機能させることができます。

ただし、配列の各要素には１つのデータしか格納できません。２つ目以降のデータを格納すると、その前に格納したデータが上書きされてしまうことになります。

なので、データの重複があることを考慮すると１次元配列の各要素をバケツとするとうまくソートできないことになります。

ソースコード

１次元配列の各要素をバケツとした場合のバケットソートを行うプログラムのソースコードは下記のようになります。

配列の各要素をバケツとしたバケットソート

void bucketSort(int a[], int num) {
    int i, j;
    int *buckets; /* バケツ */
    int max;
    int bucket_size;

    /* データの最大値を求める */
    max = 0;
    for (i = 0; i < num; i++) {
        if (max < a[i]) {
            max = a[i];
        }
    }
    bucket_size = max + 1;

    /* 最悪0からmaxのデータを格納できるようにサイズmax+1のメモリを用意する */
    buckets = (int*)malloc(sizeof(int) * bucket_size);

    for (i = 0; i < max; i++) {
        /* バケツが空であることがわかるように-1を入れておく */
        buckets[i] = -1;
    }

    /* バケツにデータを入れていく */
    for (i = 0; i < num; i++) {

        /* ラベルa[i]のバケツにa[i]のデータを入れる */
        buckets[a[i]] = a[i];
    }

    /* ラベルが小さいバケツか順にデータを取り出していく */
    j = 0;
    for (i = 0; i < bucket_size; i++) {
        /* バケツが空でないかどうかを確認 */
        if (buckets[i] != -1) {
            /* 配列aに取り出したデータを入れる */
            a[j] = buckets[i];
            j++;
        }
    }

    free(buckets);
}

ソースコードの解説

まずは引数と、この関数の前提について解説しておきます。

引数 a はソートしたいデータを格納した配列になります（今回は各データが int 型のものとして関数を作成しています）。また、引数 num はソートしたいデータの個数になります。

配列 a の全要素は “0 以上の値が格納されている” という前提のもとでソートを行う関数になっています。

関数を実行すると、配列 a のデータが “昇順に” ソートされた状態になります。

今後、バケツの実現方法に応じて様々な bucketSort 関数を紹介しますが、上記の引数や前提等に関しては全て同じになります（以降の bucketSort 関数の紹介ではこれらの説明は省略させていただきます）。

この bucketSort 関数では、まずデータの中の最大値 max を見つけ出し、続いて bucket_size = max + 1 個分の int 型の数値が格納できるように malloc 関数でメモリ確保しています。

バケツを準備する

buckets = (int*)malloc(sizeof(int) * bucket_size);

MEMO

本来であれば malloc 関数実行後は、malloc 関数でエラーが発生したかどうかを戻り値から判断する必要があります

そしてエラーの場合は、プログラムを終了するようなエラー処理を実行する必要があります

ただし今回はプログラムを簡素化するためにこのエラーの確認やエラー処理は省略していますので注意してください

malloc 関数で確保したメモリは配列同様に扱うことが可能です。この場合は int 型でサイズが bucket_size、配列名 buckets の配列と同様にして扱うことができます。

ソートを行う際には、buckets の各要素をバケツとして扱います。具体的には、buckets[x] は値が x のデータを格納するバケツとして扱います。

buckets のサイズは bucket_size であり、これは a に格納されているデータの種類とは異なります。ただし、a に格納されているデータの値は全て 0 以上という前提があるので、必ず bucket_size(max + 1) は各データが取りうる値の種類以上の数値となります（バケツは各データが取りうる値の種類分もしくはそれ以上用意する必要がある）。

MEMO

各データが取りうる値の種類数をカウントアップするよりも最大値を求める方が簡単なので、バケツのサイズは上記のように決定するようにしています

バケツとなる配列を準備した後は、まずバケツが空であることを示すために各要素に -1 を格納しています。

バケツを空にする

for (i = 0; i < max; i++) {
    /* バケツが空であることがわかるように-1を入れておく */
    buckets[i] = -1;
}

続いてソートするデータが格納された a の各要素を先頭から順にバケツに入れていきます。前述の通り、buckets[x] は値が x のデータを入れるバケツになるので、値が a[i] のデータは buckets[a[i]] に入れることになります。

バケツにデータを入れる

for (i = 0; i < num; i++) {

    /* ラベルa[i]のバケツにa[i]のデータを入れる */
    buckets[a[i]] = a[i];
}

全てのデータがバケツに入れられた後は、今度はバケツからのデータの取り出しを行なっていきます。今回は “昇順に” データをソートするため、配列の先頭から順にデータの取り出しを行なっていきます。

ただし、前述の通り、バケツが空の場合がありますので、この場合はバケツからの取り出しをスキップするようにしています。バケツが空の場合とは、buckets[i] が -1 の場合になります。

この辺りのデータの取り出しを行なっているのが下記部分になります。

バケツからデータを取り出す

j = 0;
for (i = 0; i < bucket_size; i++) {
    /* バケツが空でないかどうかを確認 */
    if (buckets[i] != -1) {
        /* 配列aに取り出したデータを入れる */
        a[j] = buckets[i];
        j++;
    }
}

取り出したデータは、取り出した順に配列 a の先頭から格納していっているので、配列 a には元々の配列 a のデータを昇順にソートした状態でデータが格納されることになります。

以上でバケツを１次元配列の各要素とした時のバケットソートによるソートは完了になります。ただし、前述の通りデータに重複がある場合はうまくソートできないので注意してください。

データの分布を考慮してバケツを準備する（分布数えソート）

次はバケツを単に配列の１つの要素とするのではなく、必要な分だけの要素をバケツとする方法を解説します。

実装の考え方

配列の各要素を１つのバケツとすると、データの重複がある場合にうまくソートできないという問題がありました。

うまくソートできないのは、バケツに入れることのできるデータが１つのみであることが原因です。要はバケツのサイズが足りなくてデータが溢れてしまっていたということですね！

なので、事前にデータの値の分布を調べ、各バケツのサイズを必要な分だけ確保するようにしてやれば、データが溢れてしまってソートが上手くいかない現象を防ぐことができます。

より具体的には、まず各値を持つデータがいくつずつ存在するかを調べます。これにより、各値のデータを入れるバケツに必要なサイズが分かります。

続いて、各値を入れるためのバケツを用意します。今回はこのバケツを、１つの配列を分割する形で用意したいと思います。ここでは、この配列を buckets とします。buckets のサイズはバケツの個数には関係なく、ソートするデータの個数となります。

配列 buckets の先頭から順に、値の小さなデータを入れるバケツ用に分割していきます。

例えば１番小さな値を持つデータが 3 つである時、その値を格納するバケツとしては、配列の要素として 3 つ必要です。なので、配列の先頭から 3 つ分を１番小さな値を持つデータ用のバケツとします。つまり、buckets[0] 〜 buckets[2] がこの１番小さな値を持つデータを入れるためのバケツとなります。

さらに、２番目に小さな値を持つデータが 2 つである時、その値を格納するバケツとしては、配列の要素として 2 つ必要です。なので、１番小さな値を持つデータを格納するためのバケツの直後の 2 つの要素を、この２番目に小さな値を持つデータを格納するためのバケツとします。つまり、buckets[3] 〜 buckets[4] がこの１番小さな値を持つデータを入れるためのバケツとなります。

こんな感じで、１つの配列を複数のバケツに分割して考えていきます。最終的には、１つの配列がデータの値の種類分のバケツに分割されます。

バケツの分割が終われば、続いてはソートするデータを全て、値に応じたバケツに入れていきます。

全てのデータをバケツに入れ終わったら次はデータの取り出しです。

配列の先頭側に小さな値のデータを格納するようになっているので、配列の先頭からデータを取り出すことでソートを行うことが可能になります。

データの値が重複する場合は、同じバケツに対して複数のデータを入れることになります。この場合は、先に入れるデータをバケツの先頭方向から入れていくことで、データの取り出し時にデータを入れた順に取り出すことができるようになります。

このように実装を行うバケットソートを、特別に「分布数えソート」「計数ソート」と呼ぶことがあります。

ソースコード

データの分布を考慮してバケツを準備するようにした場合のバケットソート（分布数えソート）を行うプログラムのソースコードは下記のようになります。

分布数えソート

void bucketSort(int a[], int num) {
    int *buckets; /* バケツ */
    int *start; /* 各バケツの先頭位置 */
    int *count; /* 各値の出現数 */

    int i, j;
    int bucket_size;
    int max;

    /* データの最大値を求める */
    max = 0;
    for (i = 0; i < num; i++) {
        if (max < a[i]) {
            max = a[i];
        }
    }
    bucket_size = max + 1;

    /* バケツの数に応じてメモリを確保 */
    count = (int*)malloc(sizeof(int) * bucket_size);
    start = (int*)malloc(sizeof(int) * bucket_size);

    /* ソートするデータの数に応じてメモリを確保 */
    buckets = (int*)malloc(sizeof(int) * num);
    
    /* 各値の出現数を0に初期化 */
    for (i = 0; i < bucket_size; i++) {
        count[i] = 0;
    }

    /* a[i]の値がいくつあるかをカウント */
    for (i = 0; i < num; i++) {
        count[a[i]]++;
    }

    /* 配列上のラベルiのバケツの先頭位置を決める */

    /* 値0のデータを入れるバケツは配列の先頭とする */
    start[0] = 0;
    for (i = 1; i < bucket_size; i++) {
        /* 値iのデータを入れるバケツは、
           値i-1のデータを入れるバケツの先頭位置から
           値i-1のデータの個数ずらした位置とする */
        start[i] = start[i - 1] + count[i - 1];
    }

    /* ソートを実行 */
    for (i = 0; i < num; i++) {

        /* 対応するバケツにデータを格納 */
        buckets[start[a[i]]] = a[i];

        /* 数値a[i]の格納先を１つ後ろにずらす */
        start[a[i]]++;
    }

    /* ラベルが小さいバケツから順にデータを取り出していく */
    j = 0;
    for (i = 0; i < num; i++) {
        /* 配列aに取り出したデータを入れる */
        a[j] = buckets[i];
        j++;
    }

    free(count);
    free(start);
    free(buckets);
}

ソースコードの解説

この bucketSort 関数では、まずデータの中の最大値 max を見つけ出し、用意するバケツの数 bucket_size を max + 1 で計算しています。

続いて、下記の３つの用途のメモリを確保し、それぞれをポインタで指して配列と同様に扱えるようにしています。

各値のデータの個数を格納するためのメモリ（count）
各値のデータを格納するバケツの配列上の位置を格納するためのメモリ（start）
複数のバケツとしてデータを格納するためのメモリ（buckets）

さらに、下記で各値を持つデータの個数をカウントしています。

各値を持つデータの個数を数える

/* 各値の出現数を0に初期化 */
for (i = 0; i < bucket_size; i++) {
    count[i] = 0;
}

/* a[i]の値がいくつあるかをカウント */
for (i = 0; i < num; i++) {
    count[a[i]]++;
}

さらに、この各値のデータの個数より、下記の部分で配列 buckets を複数のバケツに分割しています。

配列を各バケツに分割する

start[0] = 0;
for (i = 1; i < bucket_size; i++) {
    /* 値iのデータを入れるバケツは、
       値i-1のデータを入れるバケツの先頭位置から
       値i-1のデータの個数ずらした位置とする */
    start[i] = start[i - 1] + count[i - 1];
}

バケツに分割といっても配列を本当に分割しているわけではなく、バケツに分割したように扱えるようにバケツの先頭位置を決定しているだけです。

上記により、値 x を持つデータのバケツの先頭位置は start[x] に格納されることになります。つまり、値 x のデータを入れるバケツの配列上の先頭位置は buckets[start[x]] になります。

実際にこのバケツにデータを入れる処理を行なっているのは下記部分になります。

バケツにデータを入れる

for (i = 0; i < num; i++) {

    /* 対応するバケツにデータを格納 */
    buckets[start[a[i]]] = a[i];

    /* 数値a[i]の格納先を１つ後ろにずらす */
    start[a[i]]++;
}

buckets[start[a[i]]] に値 a[i]] を格納するようにしているので、値に応じて入れる先のバケツが切り替えられながら配列にデータが格納されることになります。

また、配列の同じ要素にデータを上書きしてしまうと事前に格納していたデータが消えてしまうことになるので、そうならないよう、値 a[i] のデータを buckets[start[a[i]]] に格納した後には start[a[i]]++ を行ない、次に a[i] のデータを格納する位置をずらすようにしています。

データを全てバケツに入れた後は、buckets の先頭から順にデータを取り出し、そのデータを配列 a に格納しています。これにより配列 a にはソート済みのデータが格納されることになります。

バケツからデータを取り出す

j = 0;
for (i = 0; i < num; i++) {
    /* 配列aに取り出したデータを入れる */
    a[j] = buckets[i];
    j++;
}

データを入れるときにバケツを動的に追加する

最後に紹介するのは、”リスト構造” を利用してバケツを動的に追加しながらデータを入れていく方法になります。

実装の考え方

先程のデータの分布を考慮してバケツを準備するでは、事前に各値のデータの個数を数える必要がありました。

今回は、事前に各データの個数を数えることなく、重複のあるデートもソートできるバケットソートの実装方法を紹介していきます。

今までの方法では、バケツを全て用意してからデータをバケツに入れていきましたが、今回の方法では、データを入れる時にバケツを用意するようにします。つまり、バケツが必要になった際にバケツを動的に追加する方法になります。

この動的なバケツの追加を行うために、今回はリスト構造を利用したいと思います。リスト構造は後からバケツのようなメモリを追加するのに便利なデータ構造です。

リスト構造についてもし詳しく知りたい方は、下記ページで解説していますのでこちらのページを読んでみていただければ幸いです。

【C言語】リスト構造について分かりやすく解説【図解】

リストは “データとデータを連結させる” データ構造になります。今回はバケツとバケツを連結させる目的でリスト構造を用います。

ただし、リストで連結させるのは同じ値のデータを入れるバケツ同士のみとします。なので、取りうる値の種類分（もしくはそれ以上）の数のリストを用意することになります。

さらに、これらのリストの先頭のアドレスを配列で管理するようにします。この配列の先頭から順に、小さな値のデータを格納するバケツのリストの先頭のアドレスを格納するようにします。

そして、ある値のデータをバケツに入れる際には、その値に対応するリストの一番後ろにバケツを追加し、追加後にそのバケツにデータを入れるようにします。

これを繰り返せば、配列からどんどんリストが伸びていく感じになります。配列の前側から伸びているリストは、より小さな値が入れられたバケツのリストになります。また、リストの後ろ側のバケツには、後から追加されたデータが入ることになります。

ですので、配列の先頭から順に、さらにリストの先頭から順にバケツからデータを取り出すようにすれば、取り出した後のデータが昇順にソートされることになります。

C言語の場合、リスト構造を扱うためにはリスト構造を自身で実装する必要があるので、この方法でバケットソートを実装すると若干ソースコードが複雑になります。例えば Python などのように、リストが初めから用意されている言語だと、もっとシンプルにプログラミングすることが可能になります。

ソースコード

リストを用いたバケットソートを行うプログラムのソースコードは下記のようになります。

リストを用いたバケットソート

/* リストの各ノード */
struct NODE {
    struct NODE *next; /* 次の"同じ値を入れるバケツ"のアドレス */
    int data; /* バケツ */
};

void bucketSort(int a[], int num) {
    struct NODE **list;
    struct NODE *node;
    struct NODE *new, *del;
    int i, j;
    int max;
    int bucket_size;

    /* 取りうる値の種類の最悪値を求める */
    max = 0;
    for (i = 0; i < num; i++) {
        if (max < a[i]) {
            max = a[i];
        }
    }
    bucket_size = max + 1;

    /* リストの先頭のアドレスを格納するための配列を確保 */
    list = (struct NODE**)malloc(sizeof(struct NODE*) * bucket_size);

    for (i = 0; i < bucket_size; i++) {
        /* 各ノードへのポインタをNULLにせっt */
        list[i] = NULL;
    }

    /* データをバケツに入れる */
    for (i = 0; i < num; i++) {
        /* 新しいノードを作成する */
        new = (struct NODE*)malloc(sizeof(struct NODE));
        new->next = NULL;
        new->data = a[i]; /* バケツにデータを入れる */

        if (list[a[i]] == NULL) {
            /* a[i]を入れるバケツのノードがまだない場合 */

            /* 配列のa[i]要素にノードを指させる */
            list[a[i]] = new;
            
        } else {
            /* a[i]を入れるバケツのノードがすでにある場合 */

            /* 一番最後ノードまで辿る */
            node = list[a[i]];
            while (node->next != NULL) {
                node = node->next;
            }

            /* 一番最後のノードの後ろに新しいノードをセットする */
            node->next = new;

        }
    }

    /* データを取り出してaに格納 */
    j = 0;

    /* 配列の先頭から順にリストを走査 */
    for (i = 0; i < bucket_size; i++) {
        
        node = list[i];
        while (node != NULL) {
            /* リストの先頭から順にデータを取り出し */
            a[j] = node->data;
            j++;

            /* リストの次のノードを辿る */
            node = node->next;
        }
    }

    /* リストのノードを全て削除 */
    for (i =0; i < bucket_size; i++) {
        /* 配列の先頭から順にリストを走査 */
        node = list[i];
        while(node != NULL) {
            /* 注目ノードのアドレスを覚えておく */
            del = node;

            /* リストの次のノードを辿る */
            node = node->next;

            /* 注目ノードを削除する */
            free(del);
        }
    }

    /* 配列を削除する */
    free(list);
}

ソースコードの解説

まずは最初に定義している struct NODE 型について解説します。

この struct NODE 型がリストのノードを表す構造体になります。このバケットソートにおいては、このノードをバケツとして扱います。

data がバケツ自体を表しており、この data へのデータの格納が、バケツにデータを入れる処理となります。

また nextは次のバケツを指すポインタになります。この nextでバケツを連結させることでリスト構造体を実現していきます。

続いてソートを実行する bucketSort 関数について解説していきます。

この bucketSort 関数では、下記で各リストの先頭アドレスを格納するための配列を作成しています（メモリを確保している）。

list = (struct NODE**)malloc(sizeof(struct NODE*) * bucket_size);

この配列のサイズは bucket_size で、bucket_size は全データの値の 最大値 + 1 としています。また、まだリストはない状態なので、配列の全要素には NULL 格納しています。

for (i = 0; i < bucket_size; i++) {
    /* 各ノードへのポインタをNULLにせっt */
    list[i] = NULL;
}

続いてデータをバケツに入れる処理を行なっていきます。前述の通り、この方法ではデータを追加する際に、そのデータを入れるためのバケツを追加してからデータをバケツに入れるようにします。

このバケツの追加と、バケツにデータを入れる処理を行なっているのが下記部分になります。

バケツを追加してデータを入れる

new = (struct NODE*)malloc(sizeof(struct NODE));
new->next = NULL;
new->data = a[i]; /* バケツにデータを入れる */

バケツの追加は struct NODE 型のデータのメモリを malloc 関数で確保することで実現しています。さらに、バケツにデータ処理を入れる処理は data メンバへのデータ a[i] の格納により実現しています。

後から追加したバケツはリストの終端に連結するため、そのバケツが終端であることがわかるように next には NULL を格納しています。

これでバケツを追加し、バケツにデータが入ったことになるのですが、まだバケツがリストに連結されていないのでこのバケツは宙ぶらりんの状態になっています。

なので、次はこのバケツをリストに連結する処理を行います。これは下記部分で行なっています。

バケツをリストを連結する

if (list[a[i]] == NULL) {
    /* a[i]を入れるバケツのノードがまだない場合 */

    /* 配列のa[i]要素にノードを指させる */
    list[a[i]] = new;
            
} else {
    /* a[i]を入れるバケツのノードがすでにある場合 */

    /* 一番最後ノードまで辿る */
    node = list[a[i]];
    while (node->next != NULL) {
         node = node->next;
    }

    /* 一番最後のノードの後ろに新しいノードをセットする */
    node->next = new;

}

値 a[i] のデータを入れるバケツをリストに連結する処理は、バケツの連結先となるリストがまだない場合（list[a[i]] == NULL）と、すでにそのバケツの連結先となるリストがある場合（list[a[i]] != NULL）とで異なります。

前者の場合、まだ値 a[i] のデータを入れるバケツのリストが存在していないので、今回追加したバケツがリストの先頭になります。なので、今回追加したバケツ new が値 a[i] のデータを入れるバケツのリストの先頭であることが後からわかるように、list[a[i]] に new のアドレスを格納します。

後者の場合、今回追加したバケツを list[a[i]] が指すリストの終端に追加します。この終端まで辿る処理が下記になります。リストの終端のバケツであることは、next が NULL であるかどうかで判断することができます。

リストの終端までたどる

node = list[a[i]];
while (node->next != NULL) {
    node = node->next;
}

上記のループが完了したときの node がリストの終端のバケツとなりますので、このバケツの後ろ側、つまりnode->next に新たに追加したバケツのアドレス new をセットすることで、リストの終端に新たに追加したバケツを連結しています。

上記の処理をソートしたい全てのデータに対して繰り返し実行することで、データが全てバケツに入れられることになります。

なので、続いてはデータの取り出しを行なっていきます。このデータの取り出しを行なっているのが下記部分になります。

データの取り出しを行う

j = 0;

/* 配列の先頭から順にリストを走査 */
for (i = 0; i < bucket_size; i++) {
        
    node = list[i];
    while (node != NULL) {
        /* リストの先頭から順にデータを取り出し */
        a[j] = node->data;
        j++;

        /* リストの次のノードを辿る */
        node = node->next;
    }
}

この i に対する for ループは、配列の先頭から最後尾の順に各リストを辿るためのループになります。

さらにリストには複数のバケツが連結されている可能性があるため、上記の while ループの中でリストの先頭から終端までバケツをたどりながらデータを取り出し、そのデータを配列 a の先頭から順に格納するようにしています。