マージソートで正しく並び替えれない

実現したいこと

配列の分割とマージを行う処理を再帰的に適用した結果としてソート済みとなった 2 つの部分配列を1つの配列にマージすることで、配列全体を降順にソートする。

前提

ここに質問の内容を詳しく書いてください。
（例）
TypeScriptで●●なシステムを作っています。
■■な機能を実装中に以下のエラーメッセージが発生しました。

発生している問題・エラーメッセージ

実行すると正しく並び替えることができていない。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
void merge(int x[], int left, int right)
{
    if (left < right)
    {
        int center = (left + right) / 2;
        int buf_a[100]; /* 作業用配列(配列の前半を一時的に格納) */
        int na = center - left + 1;
        int buf_b[100]; /* 作業用配列(配列の後半を一時的に格納) */
        int nb = right - center;
        int p, i;
        /* 配列x[]の前半と後半の要素に対して、それぞれ関数mergeを再帰的に適用*/
         if (left == right) {
        return;
    }
        merge(x, left, center);     // 左側の配列にmergeを適用する
        merge(x, center+1, right);    // 右側の配列にmergeを適用する
        /* 配列xの前半をbuf_aにコピー */
        for (p = 0, i = left; i <= center; p++, i++){
                buf_a[p] = x[i];
            }
        /* 配列xの後半をbuf_bにコピー */
        for (p = 0, i = center + 1; i <= right; p++, i++){
            buf_b[p] = x[i];
        }
        /* buf_aとbuf_bをマージしてx[]に格納 */
        int pa = 0;
        int pb = 0;
        int pc = 0;
        while (pa < na && pb < nb)
        {
            if (buf_a[pa] >= buf_b[pb])
            {
                x[pc] = buf_a[pa];
                pa++;
                pc++;
            }
            else
            {
                x[pc] = buf_b[pb];
                pb++;
                pc++;
            }
        }
        while (pa < na)
        {
            x[pc] = buf_a[pa];
            pa++;
            pc++;
        }
        while (pb < nb)
        {
            x[pc] = buf_b[pb];
            pb++;
            pc++;
        }
    }
}
int main(void)
{
    int i;
    int x[10] = {3, 2, 4, 8, 9, 1, 5, 6, 7, 10};
    int n = 10;
    merge(x, 0, 9);
    puts("配列aとbをマージして配列cに格納しました。");
    for (i = 0; i < n; i++)
    {
        printf("c[%2d] = %2d\n", i, x[i]);
    }
    return 0;
}

試したこと

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

jimbe

2023/03/29 19:09 編集

teratail はデバックしてもらう所ではありません。実行するとどうなるのでしょうか。どこまで想定通りに動作していることを確認していますか。

行動規範の内容に同意します

回答2件

ベストアンサー

merge 関数内では x は left ～ right の範囲内しか扱わないはずですが、一部そうなっていません。

投稿2023/03/30 04:09

編集2023/03/31 17:46

jimbe

総合スコア12646

C
1void merge(int x[], int left, int right)
2{
3    if (left < right) // *** この条件が成立しているなら ***
4    {
5        int center = (left + right) / 2;
6        int buf_a[100]; 
7        int na = center - left + 1;
8        int buf_b[100];
9        int nb = right - center;
10        int p, i;
11        /* 配列x[]の前半と後半の要素に対して、それぞれ関数mergeを再帰的に適用*/
12        if (left == right) { // *** ここには飛び込まないのでは? ***
13            return;
14        }
15        ...