C言語のアルゴリズム、マージソートについて質問です。
例えば下のプログラム
#include <stdio.h>
void merge(int first, int last, int *data, int *work);
int main(void)
{
int data[9] = {1,8,3,6,5,4,7,2};
int work[9];
int i;
merge(0,8,data,work);
for(i = 0;i < 9;i++) printf("%d",data[i]);
return 0;
}
void merge(int first, int last, int *data, int *work)
{
int middle, mae, ato, i;
if (first == last)
{
return;
}
middle = (first + last) / 2;
merge(first, middle, data, work);
merge(middle + 1, last, data, work);
i = first;
mae = first;
ato = middle + 1;
while (mae <= middle && ato <= last)
{
if (data[mae] <= data[ato])
{
work[i] = data[mae];
i++;
mae++;
}
else
{
work[i] = data[ato];
i++;
ato++;
}
}
while (mae <= middle)
{
work[i] = data[mae];
i++;
mae++;
}
while (ato <= last)
{
work[i] = data[ato];
i++;
ato++;
}
for (i = first; i <= last; i++)
{
data[i] = work[i];
}
}
まずfirst=0,last=8でmerge関数に入り関数内8行目でmiddle=4となり、
10行目でfirst=0,last=4でmergeに入り同じく8行目でmiddle=2となり、
同じく10行目でfirst=0,last=2でmergeに入り同じく8行目でmiddle=1となり、
同じく10行目でfirst=0,last=1でmergeに入り同じく8行目でmiddle=0となり、
同じく10行目でfirst=0,last=0でmergeに入り3行目のifでreturnします。
そして前回のfirst=0,last=1,middle=0のmerge10行目に戻り,
12行目でfirst=1,last=1でmergeに入り3行目のifでreturnし、
12行目以下の作業をします。
そのまま一番下までいったあとはどうなるのでしょうか?
また上で書いた手順もあっている自信はあまりないので
ご指摘お願いします。
A 回答 (5件)
- 最新から表示
- 回答順に表示
No.5
- 回答日時:
#3です。
まず、字数の関係で載せられなかった実行結果を示しておきます。----- 実行結果 -----
first=0 last= 7 middle= 3
first=0 last= 3 middle= 1
first=0 last= 1 middle= 0
first=0 last= 0 ...return
first=1 last= 1 ...return
merging 0 1 (case middle 0 [0 - 1])
first=2 last= 3 middle= 2
first=2 last= 2 ...return
first=3 last= 3 ...return
merging 2 3 (case middle 2 [2 - 3])
merging 0 2 (case middle 1 [0 - 3])
first=4 last= 7 middle= 5
first=4 last= 5 middle= 4
first=4 last= 4 ...return
first=5 last= 5 ...return
merging 4 5 (case middle 4 [4 - 5])
first=6 last= 7 middle= 6
first=6 last= 6 ...return
first=7 last= 7 ...return
merging 6 7 (case middle 6 [6 - 7])
merging 4 6 (case middle 5 [4 - 7])
merging 0 4 (case middle 3 [0 - 7])
Result:
1 2 3 4 5 6 7 8
答えは、肝心の境界値があなたの質問と異なっています。
答えは
http://www.codereading.com/algo_and_ds/algo/merg …
の通り、
first=1,last=1でdata[0-1]間のmergeに入り3行目のifでreturnし、
12行目以下の作業、すなわち mergingを行います。
そのまま一番下にいったあとは、次の配列data[2-3]について同じ操作を繰り返します。
No.3
- 回答日時:
データ数と出力 for() の内容があっていませんが、プログラム間違ってません?
以下のプログラムを実行してみると、再帰ゆえ、あなたが答えるほど内容は簡単ではないようです。
http://www.codereading.com/algo_and_ds/algo/merg …
#include <stdio.h>
#define KOSU 8
void merge(int, int, int *, int *);
int main(void)
{
int data[KOSU] = {1,8,3,6,5,4,7,2};
int work[KOSU];
int i;
merge(0,KOSU-1,data,work);
printf("Result:\n");
for(i = 0; i < KOSU; i++) printf("%d ",data[i]);
printf("\n");
return 0;
}
void merge(int first, int last, int *data, int *work)
{
int middle, mae, ato, i;
printf("\tfirst=%d \tlast= %d ", first, last);
if (first == last) {
printf("\t...return\n");
return;
}
middle = (first + last) / 2;
printf("\tmiddle= %d\n", middle);
merge(first, middle, data, work);
merge(middle + 1, last, data, work);
i = mae = first;
ato = middle + 1;
printf("\tmerging %d %d (case middle %d [%d - %d])\n",
mae, ato, middle, first, last);
while (mae <= middle && ato <= last) {
if (data[mae] <= data[ato]) work[i++] = data[mae++];
else work[i++] = data[ato++];
}
while (mae <= middle) work[i++] = data[mae++];
while (ato <= last) work[i++] = data[ato++];
for (i = first; i <= last; i++) data[i] = work[i];
}
No.2
- 回答日時:
どうなるでしょうかって
実行させてみればよいではありませんか
それから ソースがよみづらいです
インデントをつけられてはいかがでしょうか
途中の過程を追いかけたかったら
デバッグツールを使うのも一法かと
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# 10個の実数に対する降順ソート結果を出力するプログラムを作りたいのですが、以下のプログラムをどう直せ 1 2022/07/09 22:16
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# C#の検索プログラムの問題で下の写真についてなのですが実行した時にfirst、last、center 2 2022/10/13 09:36
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- Java javaでのプログラム(配列)について質問です. 2 2022/10/14 22:27
- FX・外国為替取引 mql4のコンパイルエラー箇所の修正お願いします。 1 2023/03/15 16:14
- C言語・C++・C# C#テキストボックスの文字を配列にいれてその後表示する 4 2022/07/17 04:47
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語での引数の省略方法
-
「指定されたキャストは有効で...
-
#define _CRT_SECURE_NO_WARNIN...
-
複数桁10進数の*桁目だけを抽出...
-
(int *)の意味
-
卒業研究でよく分からないとこ...
-
ラップ関数とはどんなものですか?
-
if と配列の組み合わせ
-
C言語初心者です、、、お助けく...
-
【C++】関数ポインタの使い方
-
アスタリスクで正方形
-
インライン展開されているか確...
-
構造体の勉強中です 合計点の高...
-
異なる文字列のマッチングを、D...
-
数字列を3桁ごとにカンマで区切...
-
C言語 配列と関数の練習問題
-
C言語で三目並べをするプログラ...
-
入力を待たずにstdinの監視をし...
-
ファイルから読みこむ方法
-
課題でつまってます・・・
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「指定されたキャストは有効で...
-
C言語での引数の省略方法
-
複数桁10進数の*桁目だけを抽出...
-
#define _CRT_SECURE_NO_WARNIN...
-
ラップ関数とはどんなものですか?
-
卒業研究でよく分からないとこ...
-
【C++】関数ポインタの使い方
-
実数の整数部,小数部の取得
-
std::set<int> で、ある値が何...
-
C言語 エラーの原因がわからな...
-
c言語
-
system関数がうまくいかない
-
C++でvectorにテキストファイル...
-
acceptをalarmでタイムアウトさ...
-
if と配列の組み合わせ
-
return 1L
-
「{ } で囲むだけ」は正しい?
-
(マルチスレッド)_beginthrea...
-
PowerShellがうまくいかない
-
このプログラミング誰か教えて...
おすすめ情報