忙しい現代人の腰&肩のお悩み対策!

バブルソートと選択法について、交換回数がわかりません。
比較回数については、ネットで検索したり、本に載っているので分かりやすいのですが、交換回数があまり載っていなく…。

選択法の交換回数の最大値は、n-1でしょうか?
バブルソートの交換回数の最大値は、nでしょうか?

交換回数については、選択法のほうがバブルソートより少なくてすむそうですが、上の答えでいいのかわかりません。

どなたか教えてください。お願いしますm(_ _)m

このQ&Aに関連する最新のQ&A

A 回答 (1件)

アルゴリズムで違うような気がしますが、


選択法というのが、未決定のn個のリストから最小値を決定し、その最小値の位置のデータと交換するというようなアルゴリズムであるなら、
最悪の場合、それぞれのデータを交換する必要がありますが、最後の1コは、必然的に位置が決まるので交換しないので、
選択法の場合:n-1 回

バブルソートを隣接するデータを大小関係で交換するアルゴリズムだとすると、
最悪の場合、
最初の1つのデータが決まるのにn-1回の交換が必要で
次のデータが決まるのにn-2回の交換が必要で

最後のデータが決まるのに1回の交換が必要なので
k=1~n-1Σk
バブルソートの場合:n(n-1)/2回
になると思います。
    • good
    • 1
この回答へのお礼

ありがとうございました!!

お礼が遅くなりましてすみませんでした。


交換回数を知りたかったのでとても助かりました。m(_ _)m

お礼日時:2006/05/03 08:01

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qマージソートの計算量について-O(n*logn)

マージソートの計算量はO(n*logn)ですが、なぜそうなのかが理解出来ません。要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となり、n=2^x, x=lognとなるところまでは理解出来ました。しかし更にnをかける必要があるのはどうしてでしょうか。要素数が1になるまで分割した後に、小さい順番に比較しながら統合して行く作業があり、これにも当然ランニングタイムがかかるのはわかりますがなぜこの要素の比較コスト?が*nなのでしょうか。
またウェブで調べると、他にもT(n)=2T(2/n)+O(n)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。

Aベストアンサー

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合するのにかかる時間ですが、
たとえば、16の要素をマージソートする場合を例にあげると、

・要素数が1の部分列を要素数が2の部分列に統合する時の比較回数は1回です。要素数が2の部分列は全部で8個あるので、比較回数は8回。

・要素数が2の部分列を要素数が4の部分列に統合する時の比較回数は3回です。要素数が4の部分列は全部で4個あるので、比較回数は12回。

・要素数が4の部分列を要素数が8の部分列に統合する時の比較回数は7回です。要素数が8の部分列は全部で2個あるので、比較回数は14回。

・要素数が8の部分列を要素数が16の列に統合する時の比較回数は15回です。要素数が16の列は全部で1個あるので、比較回数は15回。

以上合計すると、比較回数8+12+14+15=49回で64要素のマージソートができるわけです。

この「比較回数」を「要素数n」の式で表現するわけですが、
個々の部分列の統合時の比較回数は、要素数n、分割数kとすると、n-k回になりますから、n=2^x (x = log n) とすると、
総比較回数=Σ(k=0~x-1) (n-2^k) = n x - n + 1 = n log n - n + 1
になります。

計算量(オーダー)の議論では、次数の低い項は無視しますから、
O(n log n - n + 1) = O(n log n) になります。

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合する...続きを読む

Q線形探索(番兵法)のプログラムについて。

線形探索(番兵法)のプログラムについて考えています。

メイン関数からsearch関数に値を渡してそこで探索させるのですが、

int search(int a[], int n, int key)
{
int i = 0;

a[n] = key;

while (1) {
if (a[i] == key)
break;
i++;
}

return (i == n ? -1 : i);
}

のwhileを使ったやり方からfor文を使ったやり方に変更したいと思っています。
色々な方法でプログラムを考えてみたいので。

そうすると、なんかうまくいきません。
for文だとどのように考えたらいいのでしょうか?

Aベストアンサー

番兵法の意義からすると冗長な表現を省いた#2の方法もそう悪くはないと思いますが、ソースの見やすさを考えると、私ならwhileを使って、
while(a[i]!=key) i++;
とします。
これは、
for(;a[i]!=key;i++);
と同義ですが、whileのほうが直感的に理解しやすいかと思います(慣れれば大して変わらないですが)。
多分動作速度もあまり変わらないでしょう。
#2ぐらいの変則的な使い方ならどうということは無いですが、中にはアルゴリズムを理解するのに「解読」が必要なほど難解な表現が使われることがあります(C/C++プログラマに多いような)。
そうしたほうがソースが短くて済んだり、動作が速かったりするのですが、あまり多用するとわけのわからない代物になります。

ここの#6さんの回答とかは面白いです。
http://oshiete1.goo.ne.jp/kotaeru.php3?q=653025

初歩のforの使い方(規定回数ループさせるだけ)で番兵法は多分無理だと思います。
どうしてもループの継続条件と検索のためのif文で計2回の比較が入りますから、逐次検索と変わらなくなってしまいます。
多分ここでつまづかれていたんでしょうけど。

番兵法の意義からすると冗長な表現を省いた#2の方法もそう悪くはないと思いますが、ソースの見やすさを考えると、私ならwhileを使って、
while(a[i]!=key) i++;
とします。
これは、
for(;a[i]!=key;i++);
と同義ですが、whileのほうが直感的に理解しやすいかと思います(慣れれば大して変わらないですが)。
多分動作速度もあまり変わらないでしょう。
#2ぐらいの変則的な使い方ならどうということは無いですが、中にはアルゴリズムを理解するのに「解読」が必要なほど難解な表現が使われることがあります(C...続きを読む

Qプログラムの考え方。

コマンドラインから引数を入力してお金の種別に分類せよ。(2000円札は考えない)
main関数ではコマンドラインからの引数を判断し、引数の数や値がおかしいときにはエラーメッセージを表示する。正しいときはsyubetu関数にデータを渡してその結果を表示する。
syubetu関数は以下のとおりである。

・関数名 syubetu
・引数 金額 money(int) 金種格納 kinsyu(int*)
・戻り値 なし
・機能 金額、金種格納用ポインタを引数とし、金種ごとの枚数を計算する関数

こういう問題があって、
コマンドラインの引数に数字を入力したら
一万円札から順番に何枚あるかの種別に分けるプログラムなんですが、
その分類をどうやってさせていいのかがわかりません。

例えば13531とかいれたら
一万円 一枚
5千円 0枚
千円 3枚
5百円 1枚
百円 0枚
50円 0枚
10円 3枚
5円 0枚
1円 1枚

っと表示させます。

この分類のところはどのように考えたらプログラムできるでしょうか?
フローチャートを考えている途中なのですが、いまいち考え方がわかりません。

よろしくおねがいします。

コマンドラインから引数を入力してお金の種別に分類せよ。(2000円札は考えない)
main関数ではコマンドラインからの引数を判断し、引数の数や値がおかしいときにはエラーメッセージを表示する。正しいときはsyubetu関数にデータを渡してその結果を表示する。
syubetu関数は以下のとおりである。

・関数名 syubetu
・引数 金額 money(int) 金種格納 kinsyu(int*)
・戻り値 なし
・機能 金額、金種格納用ポインタを引数とし、金種ごとの枚数を計算する関数

こういう問題があって、
コマンド...続きを読む

Aベストアンサー

こん**は

>特に「j/=10」や、「money%(2*j)/j」の処理の意味>がわかりません。

No.5の回答は
j/=10;

j=j/10;
と同じ意味です。
jは10分の1されていく変数ですね。

money%(2*j)/j; ←5系
money%(5*j)/j; ←1系
自分より1個大きい紙幣や硬貨の余りを自分自身で割って、枚数を出している訳です。
また、10000という、自分より1個大きい紙幣や硬貨が存在しないので、別に分けている訳ですね。
moneyの引き算をやってしまうと、10000の場合と、5000,500,50,5の場合と、1000,100,10,1の場合に分けられませんね。
そこで、
kinsyu[0] = money/10000 ;
これで、一万円札の枚数、
for (i=1,j=5000 ;i<9 ;i+=2,j/=10) kinsyu[i] = money%(2*j)/j ;
これで、五千円札、五百円玉、五十円玉、五円玉の枚数、
for (i=2,j=1000 ;i<9 ;i+=2,j/=10) kinsyu[i] = money%(5*j)/j ;
これで、千円札、百円玉、十円玉、一円玉の枚数となる訳です。

No.6の回答は
1系と5系を同じループで行う事が出来ないかを考えた結果です。
for (i=0,j=10000,k=2 ;i<9 ;kinsyu[i]=money/j,money%=j,i++,j/=k,k=7-k);
これを理解するには、i,j,k,moneyがどのように変化していくのかを表にすれば解りますよ。
i  j    k  money  kinsyu[i]
0  10000  2  13531  1
1  5000   5  3531   0
2  1000   2  3531   3
3  500   5  531   1
4  100   2  31    0
5  50    5  31    0
6  10    2  31    3
7  5    5  1    0
8  1    2  1    1

こん**は

>特に「j/=10」や、「money%(2*j)/j」の処理の意味>がわかりません。

No.5の回答は
j/=10;

j=j/10;
と同じ意味です。
jは10分の1されていく変数ですね。

money%(2*j)/j; ←5系
money%(5*j)/j; ←1系
自分より1個大きい紙幣や硬貨の余りを自分自身で割って、枚数を出している訳です。
また、10000という、自分より1個大きい紙幣や硬貨が存在しないので、別に分けている訳ですね。
moneyの引き算をやってしまうと、10000の場合と、5000,500,50,5の場合と、1000,100,10,1...続きを読む

Qmain関数終了時のreturnの意味は?

質問の題名通り、main関数終了時のreturnの意味が知りたいです。いつもは参考書に書いてある通り、return 0とやっていたのですが、参考書のサンプルプログラムでreturn 1というのがでてきた為、少し混乱しました。
参考書に説明が載っていないのでmain関数内でのreturnの意味をご教授願いたいです。よろしくお願いいたします。

Aベストアンサー

# 4です。

まず、0を返そうが、1を返そうが、そのプログラム自体の内部的な動作は通常変わりません。
戻り値で動作が変わる可能性があるのは「そのプログラムを呼び出したプログラム側」です。

例えば、make から呼び出された場合にそのプログラムが0以外が返したら、makeは「そのプログラムは失敗した」と考えて、処理を中断したりします。(続けて欲しいなら「成功」を返す、こういうために使います)
コマンドラインからあなたが手で入力したのなら、何も起きないかもしれません。

1を伝えられたOSが何をするかは環境(OS)によります。
gccは、Windows版もLinux版も各UNIX版もあるようなコンパイラですから、その版によって違う可能性があります。
ちなみに、手元の Minimalist GNU for Windows では 1 は EXIT_FAILURE でした=つまり前述のような失敗。
別のOS上のgccでは別の値にポートされている可能性も否定はできません。

C言語が保証しているのは、EXIT_SUCCESSを返したとき、その環境では成功と判断してくれるだろう値を返すことと、EXIT_FAILUREのときは失敗と判断してくれるだろう値を返すことだけです。
0は通常EXIT_SUCCESSですが、1はEXIT_FAILURE とは限りません(現実的には 0 と 1 が大半だと思いますが、EXIT_FAILUREが-1とかでも違反ではないです)。
但し、実際に判断できるかはOSにもよりますし、呼び出したプロセスがどう判断するかにもよります。

なお、Windows や Linux, その他私の知っている UNIX では、1を返されたからといって必ず何かが行われるということはありません。
前述のように、別のプログラム等から呼び出された場合に、そのプログラムが失敗と判断して何か処理を行う可能性はありますが、これらはあくまで呼び出し元のプログラムによります。
ITRON等の組込みOSでは、main が値を返す事は通常ありません。

憶測ですが、参考書のサンプルで return 1;となっているのは、例えば argv が求めているものと違うとか、fopen に失敗したとか、そういうケースではありませんか。
そういう異常処理が発生した場合に、もしも呼び出したプログラムがいたらそれを伝えられるように、EXIT_SUCCESS (0)以外の値を返すのは慣習です。
具体的にどんな値を返すかは、プログラムの設計次第になってしまいますが、1や-1を返したり、失敗原因ごとに決めた値を返したりします。
汎用性を重視するならEXIT_FAILURE等もありますが、知名度もやや低いですし、0以外なら何でもいいという認識の人も多いように思いますので、サンプルは単に1を返しているのではないかと。

# 4です。

まず、0を返そうが、1を返そうが、そのプログラム自体の内部的な動作は通常変わりません。
戻り値で動作が変わる可能性があるのは「そのプログラムを呼び出したプログラム側」です。

例えば、make から呼び出された場合にそのプログラムが0以外が返したら、makeは「そのプログラムは失敗した」と考えて、処理を中断したりします。(続けて欲しいなら「成功」を返す、こういうために使います)
コマンドラインからあなたが手で入力したのなら、何も起きないかもしれません。

1を伝えられたOSが...続きを読む

QC言語 配列の長さの上限

C言語で配列Array[N]の長さNの上限っていくらなんでしょうか?
もし可能なのであれば上限を2147483647にしたいのですが、方法を教えてください。

Aベストアンサー

そもそもWindowsの32bit版はアプリが仮想メモリ空間を2GBしか使えません。2GBを超えるには64bit版が必要です。
たとえ64bit版OSだとしても添え字が2147483647って、単純なintの配列だとしても4x2147483647=8GB必要ですね。実メモリ16GBとかのPCを用意しますか?
そもそも配列で2147483647個必要なアルゴリズムに問題ありだと思います。

QHTMLフォームのSELECTの幅を一定にするためには?

HTMLフォームのSELECTの幅を一定にするためにはどのようにすれば
いいのでしょうか?

CSS等で設定できるとありがたいのですが、やり方がわかりません。

Aベストアンサー

<select style="width: 200px">

Qバブルソートとクイックソート

まだソートについて勉強し始めたばかりですが
バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し
クイックソートはそれほど増加しないのはなぜでしょうか??
検索してみてもプログラムが書いてあってよくわからないので...

根本的なところなのでしょうがどなたか教えてください!

Aベストアンサー

では「計算量」というキーワードも追加して検索してください。
また、計算量を表わすのに使われる「オーダー」「ランダウの漸近記法」についても調べてみてください。

おおざっぱに言うと

まじめに比較すれば、
一つ目と残りn-1個の比較
2つ目とそれ以降のn-2個の比較
...
と、要素数nの二乗に比例した回数の比較必要です。これがバブルソートの計算量です。

これを、大きいもの方と小さい方の半分に分けてそれぞれを並び変えれば、
1つの並び換えが(n/2)の二乗= 1/4 * nの2乗
それが大と小の2回で * 2
合わせて 1/4 * nの2乗 * 2
= 1/2 * nの2乗
とバブルソートの半分になります。その半分のものを更に半分に...とやっていくと、最後には n * log2 n に比例する値になります。 これが、クイックソートの計算量です。(正確には平均ですが)

細かい点は省略しているので、最初に書いたような検索の結果や、「アルゴリズム」について詳しく書かれた専門書などを読んでください。

QC言語 名前順にソートする方法

こんにちは。

C言語で「入力された文字列から名前順にソート」する場合、どのようにすればよろしいのでしょうか?
名前順にソートする考え方、コードを教えていただけませんか?
※qsortは使わない前提です。
私の中のイメージは「文字列[5]と文字列[4]を比較して、文字列[5]の頭文字が若い場合、交換する」といった具合なのですが、うまくコードに表すことができないです...。

ご教示お願いします><

Aベストアンサー

バブルソート?

http://www1.cts.ne.jp/~clab/hsample/Sort/Sort1.html

Qバッファとは何ですか

C言語を使用してるとバッファという言葉がよく出てきますがバッファとは何ですか
メモリとは違うものですか
訳をみても緩衝材とか一時的に蓄える場所という意味でよく分かりません
一時的でない使い方も多い気がしますが実際はどういうものですか

Aベストアンサー

#1です

寝ぼけて適当に書いたので修正。

すぐ見つけることができたもので正確なものは英語版ですがこちらくらいかも。
Data buffer - Wikipedia (en.)
http://en.wikipedia.org/wiki/Data_buffer

一応簡単なものはこちらです。
バッファとは - e-Wrods
http://e-words.jp/w/E38390E38383E38395E382A1.html

「複数の機器やソフトウェアの間でデータをやり取りするときに、処理速度や転送速度の差を補うためにデータを一時的に保存しておく記憶装置や記憶領域のこと。」
が現在の基本定義です。処理速度・転送速度の差のための緩衝材的な意味です。

昔はソフトウェアとハードウェア間に使うデータでソフトウェア側がデータを受け取るか、整形して送信するときに使うメモリ領域が基本的にバッファでした。
マルチプロセッサ・マルチタスクの時代になってくると、ソフトウェア間の処理速度の違いを吸収するために使うメモリ領域にもバッファという言葉が使われるようになりました。ソフトウェア間で逐次(FIFO)処理されるデータのためのメモリ領域がこちらの使われ方の主戦場といったところでしょうか。

ソフトウェア間でただ一括転送されるデータならバッファという言葉は誤用ということになるのですが、よく誤用されます。

#1です

寝ぼけて適当に書いたので修正。

すぐ見つけることができたもので正確なものは英語版ですがこちらくらいかも。
Data buffer - Wikipedia (en.)
http://en.wikipedia.org/wiki/Data_buffer

一応簡単なものはこちらです。
バッファとは - e-Wrods
http://e-words.jp/w/E38390E38383E38395E382A1.html

「複数の機器やソフトウェアの間でデータをやり取りするときに、処理速度や転送速度の差を補うためにデータを一時的に保存しておく記憶装置や記憶領域のこと。」
が現在の基本定義です。処理速度・転送速...続きを読む


人気Q&Aランキング