確率・統計の問題と解答例 [高校の統計]
問題
箱の中には、1〜N（Nは２以上）までの相異なる数字が書かれた玉がN個入っている。その箱の中から１つ取り出した玉に書かれている数字をXとし、取り出した玉を戻さず、さらにもう１つ取り出した玉に書かれている数字をYとする。
このとき、次の問に答えよ。
（１） Xの期待値（平均値）はいくらか。
（２） X＋Yの期待値（平均値）はいくらか。
（３） １回目に取り出した玉を箱に戻したあとに、さらに、２回目の玉を取り出すように変更したとする。１回目に取り出した球に書かれている数をX、２回目に取り出した書かれている数をYとしたとき、X＋Yの期待値（平均値）はいくつになるか。
N=3の場合、
（１）
（２） １回目にX、２回目にYが出た事象を(X,Y)で表すと、同様に確からしい根源事象は、つぎの４つになる。
(1,2)、(1,3)、(2,1)、(2,3)、(3,1)、(3,2)
したがって、期待値は
（３） 同様に確からしい根源事象は、次の６つになる。
(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)
したがって、期待値は
Z=X+Yとおき、確率分布を作って解くならば、次のようになるだろう。
（２） Z=X+Yとすると、確率分布は
|
Z |
3 |
4 |
5 |
|
確率p(Z) |
1/3 |
1/3 |
1/3 |
したがって、X+Yの期待値は
（３） Z=X+Yとすると、その確率分布は
|
Z |
2 |
3 |
4 |
5 |
6 |
|
確率p(Z) |
1/9 |
2/9 |
3/9 |
2/9 |
1/9 |
したがって、X+Yの期待値は
どうやら取り出した球を戻そうが（復元抽出）、戻すまいが（非復元抽出）であろうが、取り出した２つの玉に書かれた数の和の期待値は同じになりそうだ。
N個の場合
したがって答は
追加問題１
箱に１、２、・・・、N（N≧２）の数字が書かれたカードがそれぞれ１、２、・・・N枚入っているとする。このとき、次の問に答えよ。
（１） 箱に入っているカードは合計何枚か。
（２） 箱から１枚取り出したカードに書かれている数字がk（1≦k≦N）である確率を求めよ。
（３） 箱から１枚取り出したカードに書かれている数字の期待値（平均値）を求めよ。
【解答例】
（１） 
（２） kが書かれているカードはk枚あるので、確率は
（３） 期待値は
（解答例終）
追加問題２
２つの箱には１からｎまでの通し番号を書いたカードが入っている。各箱から同時に１枚ずつカードを取り出し、番号を比較して小さくない方をXとするとき、次の問に答えよ。
（１） X=kである確率をnとkで表わせ。ただし、kは整数で1≦k≦nとする。
（２） Xの期待値をnの式で表わせ。
【解答例】
（１） 
だから、
（２）
（解答例終）
（１）は、X=kになるのは、
(k,1),(k,2),・・・,(k,k),(k−1,k),(k−2,k),・・・,(1,k)
の2k−1通りだから、
としてもいいのでしょう。
さらに、確率・統計の追加問題 （２月２０日） [お前らに質問]
追加問題１
箱に１、２、・・・、N（N≧２）の数字が書かれたカードがそれぞれ１、２、・・・N枚入っているとする。このとき、次の問に答えよ。
（１） 箱に入っているカードは合計何枚か。
（２） 箱から１枚取り出したカードに書かれている数字がk（1≦k≦N）である確率を求めよ。
（３） 箱から１枚取り出したカードに書かれている数字の期待値（平均値）を求めよ。
こんな問題はチョロいというヒトは次の問題を解いてみる。
追加問題２
２つの箱には１からｎまでの通し番号を書いたカードが入っている。各箱から同時に１枚ずつカードを取り出し、番号を比較して小さくない方をXとするとき、次の問に答えよ。
（１） X=kである確率をnとkで表わせ。ただし、kは整数で1≦k≦nとする。
（２） Xの期待値をnの式で表わせ。
まぁ、ドッチもチョロい問題だろう。秒殺と行こうぜ！！
この追加問題１を解く間のBGMとして
どうしてもわからないヒトは、N=2、n=2の場合についてまず考え、次に、N=3、n=3の場合で解くように。
面倒に思えても、こうした地道なことを繰り返した奴が最後に微笑むものだにゃ。
お前らに質問！！ 統計・確率編 （２月２０日） [お前らに質問]
統計不正という事件で、何やら、世の中が騒がしいので、お前らに確率・統計の問題を一つ出すにゃ。
問題
箱の中には、1〜N（Nは２以上）までの相異なる数字が書かれた玉がそれぞれ１個ずつ、合計N個入っている。その箱の中から１つ取り出した玉に書かれている数字をXとし、取り出した玉を戻さず、さらにもう１つ取り出した玉に書かれている数字をYとする。
このとき、次の問に答えよ。
（１） Xの期待値（平均値）はいくらか。
（２） X＋Yの期待値（平均値）はいくらか。
（３） １回目に取り出した玉を箱に戻したあとに、さらに、２回目の玉を取り出すように変更したとする。１回目に取り出した球に書かれている数をX、２回目に取り出した書かれている数をYとしたとき、X＋Yの期待値（平均値）はいくつになるか。
1,2,・・・,Nだと難しいというヒトは、N=2、N＝３の場合について、考えるといいにゃ。
参考までに、
N＝２の場合、
（１） X=1、X=2の確率はともに1/2だから、期待値〈X〉は
（２） （X,Y）の組み合わせは、（1,2）、（2,1）で、確率は共に1/2だから、
（３） （X,Y）の組み合わせは、（1,1）、（1,2）,（2,1）,（2,2）で、このそれぞれの確率は1/4だから、
「組み合わせ」という言葉は誤解を招くおそれがあり、適切でないかもしれない。何か、いい表現があったら、教えろ！！
（２）は、Z=X+Yとおくと、Z=3で、この確率は１だから、〈Z〉=〈X+Y〉=3
（２）は、Z=X+Yとおくと、確率分布が
|
Z |
2 |
3 |
4 |
|
確率p(Z) |
1/4 |
1/2 |
1/4 |
となるので、期待値は
と解くこともできる。
この場合、（２）と（３）は同じになるようですが、N=3の場合はどうなんだろうね。
より一般のNの場合、どうなるんだろう。
つまり、
１回目に取り出した球を箱に戻してから改めて２回目の球を取り出しても（復元抽出）、戻さずに２回目の球を取り出しても（非復元抽出）、２回取り出した球に書かれている数の和の期待値（平均）は変わらないのであろうか。
ちなみに、
のときの確率を
とすると、この期待値（平均値）
は
ただし
で定義されるにゃ。
期待値を表す記号を
と表す流儀もあるので、好きな方を選ぶといいにゃ。
Golden BallとGold Ballの違いってわかるケロか。
この２つは意味が違うにゃ。
その回答が正しかろうが、間違っていようが、その回答を清書した上に、ブログの記事としてアップするにゃ。
挿入法 [数値解析]
挿入法
基本選択法よりも、さらに、効率のよい整列法である挿入法について、{4,2,5,1,3}を例に説明する。
まず、{4,2,5,1,3}の部分列（部分集合）である{4,2}に注目し、最後尾の要素2の挿入箇所を探し、そこに２を挿入すると
{4,2}→{2,4}
になり、{4,2}の並び替えが終了する。
次に、{2,4,5}の最後尾の５の挿入箇所を探し、そこに１を挿入する。すると、次のようになる。
{2,4,5}→{2,4,5}
同様に、
{2,4,5,1}→{1,2,4,5}
最後に、最後尾の３の挿入箇所を探し、そこに３を挿入すると、
{1,2,4,5,3}→{1,2,3,4,5}
と、{4,2,5,1,3}を昇順に整列することができる。
一般に、
の場合、
i=2,3,・・・,nに対して、
部分列
における
の挿入箇所を探索し、そこにを挿入することによって、整列することができる。
この手順を、アルゴリズム的に書くと次のようになる。
do i=2, 3, ・・・, n
do j=i, i−1, ・・・, 2
a(j−1)>a(j)ならば、a(j−1)とa(j)を交換
end do j
end do i
この方針に基づいてプログラムを書くと、次のようになる。
parameter(n=5)
integer a(n)
integer w
a(1)=4; a(2)=2; a(3)=5 ; a(4)=1; a(5)=3
do i=2,n
do j=i,2,-1
if(a(j-1).gt.a(j)) then ! a(j-1)とa(j)の比較
w=a(j); a(j)=a(j-1); a(j-1)=w ! a(j-1)とa(j)の交換
end if
end do
end do
write(*,*) a
end
このプログラムで昇順にデータを整列できるのですが、たとえば、
{2,4,5}
のように整列の必要のない部分列に関しては、整列の処理を省くことができるので、次のようにプログラムを改良することできる。
parameter(n=5)
integer a(n)
integer w
a(1)=4; a(2)=2; a(3)=5 ; a(4)=1; a(5)=3
do i=2,n
do j=i,2,-1
if(a(j-1).gt.a(j)) then ! a(j-1)とa(j)の比較
w=a(j); a(j)=a(j-1); a(j-1)=w ! a(j-1)とa(j)の交換
else
exit ! 並び替えの必要がないのでループから抜ける
end if
end do
end do
write(*,*) a
end
これで無駄な、無意味な挿入箇所の探索省くことが可能となり、より高速に並び替えを行うことができるのですが、a(j−1)とa(j)の交換処理には
w=a(j); a(j)=a(j-1); a(j-1)=w
と３つの作業が必要になるので、まだまだ、無駄が多い。
そこで、アルゴリズムを次のように変更する。
do i=2, 3, ・・・, n
t=a(i)
do j=i, i−1, ・・・, 2
a(j−1)>tならば、a(j)をa(j−1)に代入 （a(j−1)を１つ後ろにずらす）
そうでなければ、ループを抜ける
end do j
tをa(j)に代入
end do i
このように変更すると、
w=a(j); a(j)=a(j-1); a(j-1)=w
を
a(j)=a(j−1)
と１つの作業にすることができる。
これで、より、高速に並び替えを行うことができる。
parameter(n=100)
integer a(n)
integer t
do i=1, n
a(i)=nrandom(n) ! 乱数を使って1〜nまでのデータの作成
end do
do i=2,n
t=a(i) ! a(i)をtにコピー
do j=i,2,-1
if(a(j-1).gt.t) then ! a(j-1)とtの比較
a(j)=a(j-1) ! a(j-1)を後方に１つずらす
else
exit ! 並び替えの必要がないのでループから抜ける
end if
end do
a(j)=t ! tを挿入
end do
write(*,100) (a(i), i=1,n)
100 format (10(i8))
end
function nrandom(n)
call random_number(x)
nrandom = n*x+1
end
慣性系について by ddt³さん [ddt³さんの部屋]
ddt^3です。呼ばれて出てきました(^^)。
プロゲラさんのもともとの話がどんなものだったかは、調べきれなかったのですが・・・。
前にも言ったように、慣性系を論理的に基礎づける事はできません。それは、次の二つの定義が循環してるからです。
［定義-1：慣性系］
自由粒子（質点）が等速直線運動を行う観測系を、慣性基準系と言う。
［定義-2：自由粒子］
慣性基準系で等速直線運動を行う粒子（質点）を、自由粒子と言う。
という訳で、慣性系を先に認めるか自由粒子を先に認めるかの、鶏と卵の後先問題になります。なのでその循環を断ち切るためには、定義-1，2で無定義用語（意味は当然分かるだろう）として使用した自由粒子を、まっさきに決めておく必要があります。多くの専門書では（ランダウでも）、自由粒子は暗黙の定義になります。
［定義-0：自由粒子］
力を受けない粒子（質点）を、自由粒子と言う。
もし定義-0を受け入れるならば、慣性系とは、力を受けない粒子が等速直線運動する観測系の事です。そして慣性系で粒子が等速直線運動するならば、その粒子に力は作用していないと結論できる事になります。
よって定義-0が慣性系の、本当の物理的定義です。定義-0こそが、理論物理と現実との接点です。つまり、「力の有る無しは、経験的に判定できるはずだ」という思いがあるのです(^^;)。
では力の有る無しは、本当に経験的に判定できるのかのでしょうか？。
17世紀にニュートンは、今風に言えば、地球が慣性系だと仮定してニュートン力学を提出します。これは、地球に対して等速直線運動するものには、力が作用していないと仮定したのと同じです。それはニュートンなりの経験事実のまとめでしたが、観測により惑星は地球に対して等速直線運動していないので、そこには力が作用しているはずです。そこから帰納的に導かれたのが万有引力の法則です。そう仮定して提出されたニュートン力学はその後、太陽系の全ての惑星運行を説明し予想し当たります。そこから暗黙に引きだされた結論は、地球は近似的な慣性系であるだと思います。
次に当時から地球の自転は知られていました。そこで慣性系における回転する場合の影響を調べてみると、遠心力とコリオリの力という慣性力の存在を導けます。遠心力による重力加速度の変化が観測されるのは20世紀に入ってからですが、コリオリの力はフーコーの実験や台風の左巻き／右巻きによって実証されて行きます。
そこから暗黙に引きだされた結論は、少なくとも太陽は地球よりもより確かな近似的慣性系である、でしょう。そして慣性系は、この宇宙にたった一個あればそれで十分なのです。何故なら慣性系に対して等速直線運動する全ての観測系は慣性基準系だからです。慣性系が一個でも判明すれば、それに対する相対運動は、原理的には観測可能なはずだからです。
という訳で、近似的慣性系は目の前に地球という形であるではないか！。それは経験的に実証されたものだ。もう少し精度が欲しいなら太陽でどうだい？。エッ、もっと？。では銀河の重心では？。
エッ、もっと？。では、現在観測可能な宇宙全ての重心というはどうだ？。地球が慣性系であろうとなかろうと観測結果により、広域な宇宙を考えれば考えるほどその平均的な動きはスローリーになって行く。その観測とは地球との相対運動ではないのか？。それはさっき原理的には観測可能と言ったものだ。
地球には、地球を近似的慣性系と言って良いだけの十分な経験的実証がある。広域な宇宙ほど平均的な動きが地球に対してスローリーになるなら、この宇宙には理想化された慣性系を仮定しても、良いのではないか？。従って、力の有る無しを経験的に判定するのは、恐らく可能であろう。
・・・これが現在の結論と思います(^^;)。
物理の慣性系って存在するケロか？ [お前らに質問]
そもそも、慣性系ってものがこの宇宙に存在するのか、疑問ですね〜。
たとえば、時刻t=0のときに座標系O-xyとO'-x'y'が一致しているとします。そして、座標系（観測系）O'-x'y'はxの正の方向に加速度αの等加速度運動しているとします。
議論を簡単にするため、質点Aはx方向には観測系O'-x'y'と同じくxの正の方向に加速度α（時刻t=0のとき、x方向の速度は０とする）で、y方向に速度vで運動しているとします。
このとき、絶対慣性系O-xy系でこの運動を観測すると、AからBに運動しているように観測されますが、観測系O'-x'y'ではA'からBに等速直線運動したように見えます。
つまり、観測系O'-x'y'と同じ加速度で運動しているものは、観測系O'-x'y'では等速直線運動しているように見える。
なお、ここでいう速度、加速度はともに座標系O-xyで測ったものとするものとする。どちらか一方を基準にしないと議論できないんで。
ネムネコは、ネムネコを中心に宇宙（の万物）は回るという天動説を信じて疑わない。ネムネコを原点にとった座標系O'-x'y'こそ正しい。
その存在を仮定するのは勝手だけれど、慣性系ってのは、そもそも、力学の理論を構築する上で必要な仮定、前提、虚構、空想物に過ぎず、その実在性は疑わしいものだにゃ。
少なくとも、このように加速度の大きさが一定で、その向きが変わらない場合、座標系O-xyが−αの加速度運動をしているのか、観測系O'-x'y'がαで加速度運動しているのかなんてわからないもん（以下の「永遠の水掛け論」を参照）。
所詮、現象説明の理論に過ぎないのに、物理学の仮定や法則などを宇宙の真理と誤解し、そう思い込み信じて疑わないのは物理屋さんの悪い癖だにゃ。
物理屋さんはもっと謙虚になるべきだと思うにゃ。
永遠の水掛け論
時刻tにおける動点PのO-xy系の座標を(x,y)、O'-x'y'の座標を〈x',y'〉に関しては、
という関係があるので、O-xyとO'-x'y'系における加速度に関しては次の関係が成立する。
これをO-xy系の運動方程式
に代入すると、
この−mαを慣性力と呼んだりするが、
とおけば、
となり、ニュートンの運動方程式が成り立つ。
と同時に、（１）式は
となるので、
O'-x'y'系の世界に住む我ら「けものフレンズ」はO-xy系の世界に住む住民に対して、「おラッチの運動方程式（３）が正しから、お前らの運動方程式（１）を（４）に直すべきだ」、「お前らこそ慣性力を加えて運動方程式を補正しろ」と主張することができるのであった。
ひょっとしたら、ddt³さんがこの件に関して何かコメント（ネムネコ天動説に対する反論かもしれない）を送ってくれるかもしれないので、 楽しみにして待つといいにゃ。さらに、アインシュタインの等価原理の説明と、その誕生の歴史的背景を説明してくれるかもしれない。
等価原理って何だ？
https://goo.gl/fQRMDN
きっと「ニュートンのバケツ」や「マッハ原理」といった面白い話が出てくると思うにゃ(^^ゞ
ブラゲロ・マムシの質問に答えたよ [ひとこと言わねば]
ブラゲロ・マムシが質問してきたので、次のように答えたにゃ。以下の文章は少し手を加えているけれど・・・。
◆ （回答№１６ cyototu ） ニュートンの法則によると力が
ゼロなら加速度もゼロで、等速直線運動する。その逆も真。だか
ら、力は働いていません（※）。
◇とは、言えません。
ニュートンの運動法則は、質点の質量をm、加速度を
、質点に作用する力を外力
とすると、
となりますが、ここに登場する質点に作用する外力は、外から質点に作用する力をすべて足しあわせたものです。
たとえば、この質点に
と
という２つの力が作用しているとします。
すると、
になります。
で、
であるとすると、
となるので、ニュートンの運動方程式は
となり、この結果、加速度a=0で、この質点は等速直線運動をすることになります。
したがって、外力
が作用していても、その和が０ならば、加速度は０になりうるんですよ。
たとえば、机の上にボールを置きますよね。これには重力がかかっていますが、この重力と大きさが等しくて向きが反対の力で机がボールを押し返すので、ボールは動かないでしょう。
このことからわかるように、机に置いたボールが静止しているからといって、このボールに外からの力が一切加わっていないわけではないのです。
外力を足しあわせたものがプラマイ０だから静止しているんですよ。
（※）
「力が働いていない」という言葉が、質点に作用する外力
の総和が、
と０であるという意味であれば正しい。
このことの省略表現として、「力は働いていません」というのであればですが・・・。
ここがポイントですが、このとき、質点は自分にという力がかかっていることはわからない。
だって、これ（静止している、等速直線運動をしているという情報）は、自分にどんな力が加わっているかどうかについて知りうる判断材料になりえないんだもん。わかるのは、自分が静止または等速直線運動しているから、外力の総和が０であるということだけ。
この他に、物体の内部に働いている内力というものがありますよね。たとえば、ボールを構成する分子は電気的な力で結びついています。ですが、内力の合計・総和が０なので、その物体は、その物体が分裂でもしない限り、内力で動いたりはしませんが・・・。ただし、絶えず、変形はするかもしれない。
また、机に置いたバナナはバナナの表面、内部にある微生物などによって腐敗します。つまり、力学的な力がバナナに作用していなくても、化学的な変化による状態変化が起こりえます。
ですから、外から力が加わっていなくても、状態や内部の状態が変化すること、内的変化は起こりえるってわけ。
寄せられた回答を見ると自由落下がどうのこうのという話が出ていますね。
「落ちる」ってどいうこと(・・?
https://nekodamashi-math.blog.so-net.ne.jp/2018-07-08-2
って、記事を昔に書いたな。
人工衛星の外に座標系を設定すると、静止衛星は等速円運動をしているので、物理学的に言うと静止衛星は落ちているんですよ。ただ、その軌道が地球の同心円であり、人工衛星が地球に衝突しないというだけの話。
また、地球表面からその人工衛星を見ると、いつも同じ位置にある（ように見える）ので静止と呼んでいるだけです。
それに、brageloneさんがいう「力」って、物理学でいうところの「力」ではないでしょう。
何かを変化させる動的な？？？を仮に「力」と名付け、物理学の諸法則のアナロジーとして議論を展開しているわけでしょう。
このアナロジーを根拠に「いまの物理学は間違っている」というわけじゃないんだから、こういう着想はあって然るべきなんじゃないかな。
私はそう思いますがね。
さらに、分裂をすれば、ものは動き出すという話を。
静止している質量Mの物体が、突如、質量m₁とm₂に分裂し、それがそれぞれv₁とv₂を持ったとする。
この分裂のときに外力が働いていないとすれば、運動量保存の法則から、
つまり、外力が一切働いていなくても、内力で分裂できれば、物は動くことができるってわけ。
ただし、このとき、質点m₁とm₂を合わせた重心の位置は移動しないことに注意。質点系に作用する内力は質点系全体の重心を移動させることはできないからね〜。
これは一種のアナロジーなんだけれど、
社会を質点系、社会を構成する個々の人々を質点とみなすと、社会全体（の重心）は変わらなくても、または、変えられなくても、社会を構成する個々の人々は互いに影響を与えつつ、それぞれが（質的に）変化しうる
って事になるのかもしれないですね〜。
このブログの訪問者は単なる孤立した質点ではなく、ネムネコとこのブログを中心に、あるいは、媒介にして、互いに結びつき、互いに影響を与え続けているのであった。
基本選択法 [数値解析]
基本選択法
前回紹介したバブルソート（Bubble Sort）は、隣接する２つの大小を比較し、順序が逆転していたならば、２つの要素を交換することのよって、データを並び替える方法であった。
そして、データの数がn個であった場合、比較回数が
回であり、データの交換回数が最悪
回になり、並び替えの効率が悪い方法であるという話をした。
隣接する２つの要素の大小関係を比較し、順序が逆転していたら交換することによって何をしているのかといえば、昇順ならば要素の最大の値のものを、降順ならば要素の値が最小のものを、その最後尾に配置してるのである。であるならば、昇順ならば要素の最大値を、降順ならば最小値を要素の中から選び出し、それを最後尾に配置すればよいということになるであろう。
たとえば、
{4,2,5,1,3}
であれば、5が最大値なので、
{4,2,5,1,3}→{4,2,3,1,5}
と並び替える。
５は最後尾に配置したので、次に、５を取り除いた
{4,2,3,1}
の最大値４を最後尾に配置する。
{4,2,3,1}→{1,2,3,4}
これで並び替えが終了。
{4,2,5,1,3}の場合、
バブルソート：６回
基本選択法：２回
と、データの交換回数を減らすことができる。
の場合、この方法のアルゴリズムは次のようなものになるであろう。
do i=n,n−1,・・・,2,1
i_max=1
do j=2,3,・・・,i
a(j)>a(i_max)ならばjをi_maxにする
end do j
a(i_max)とa(i)を交換
end do I
このFortranプログラムは次のようになる。
parameter(n=5)
integer a(n)
integer dummy
a(1)=4; a(2)=2; a(3)=5; a(4)=1; a(5)=3
do i=n, 2, -1
i_max=1
do j=2,i
if(a(j).gt.a(i_max)) then
i_max=j
end if
end do
! データの交換
dummy=a(i) !データの退避
a(i)=a(i_max)
a(i_max)=dummy
end do
write(*,*) a
end
i_max=iのとき、交換をする必要がないので、次のように変更すると、さらに速くなる。
parameter(n=5)
integer a(n)
integer dummy
a(1)=4; a(2)=2; a(3)=5; a(4)=1; a(5)=3
do i=n, 2, -1
i_max=1
do j=2,i
if(a(j).gt.a(i_max)) then
i_max=j
end if
end do
! データの交換
if(i_max.ne.i) then
dummy=a(i) !データの退避
a(i)=a(i_max)
a(i_max)=dummy
end if
end do
write(*,*) icount
write(*,*) a
end
そして、現在、最速とされるクイックソートよりも速い並べ替え法を発見すると、歴史に名を残すことができる。のみならず、特許をとれれば、巨万の富を稼げるかもしれない。
次回は、さらに速い挿入法を紹介する。
データ数が１万じゃ〜ダメだね [ひとこと言わねば]
――コンパイルするとき、速く計算してくれるように、最適化のおまじない「-O3」を唱えると、結構、速い。ただし、ここまで強力なおまじないを唱えると（最適化オプションをつけると）、コンパイラーが高速化のためにありとあらゆることをしてくれるので、書いたプログラムと出来上がったプログラムはまったく別なものになっている可能性がある（笑）――
明日、紹介する予定の基本選択法（Max法などともいう）は、データの比較回数は５０億回でバブルソートと同じなのだけれど、データの交換回数がnオーダーでn²オーダーのバブルソートより速く並び終えることができる。それでも結構時間がかかるので、本当に終わるのかと心配になってしまうほど。
だって、これを使うには再帰処理を理解しないといけない。再帰処理を使わない場合はスタックというデータ構造を理解する必要があるんだもん。それに、このアルゴリズム、整列法を説明するのは、ものすごく厄介だし・・・。文章だけでこれを説明するのは、まず、不可能だね。
この動画を見ると、並び替えの早さは、基本選択法＞挿入法＞クイックソートのように見えるけれど、これは並び替えるデータの数が多さがクイックソート＞挿入法＞基本選択法であるからそう見えるのであって、実際の並び替えの早さはクイックソート、挿入法、基本選択法の順になる。たぶん、クイックソートと挿入法ではデータの数のオーダーが少なくとも１桁は違っているはず。下手すると、２桁違うかもしれないにゃ。
#define N 100000
void BubbleSort(int *, int);
void Selection(int *, int);
void Insert(int *, int);
main() {
int a[N]={0};
int i;
for (i=0; i<N; i++)
a[i]=rand()%100000+1;
BubbleSort(a, N);
// Selection(a, N);
// Insert(a, N);
for (i=0; i < N; i++) {
printf("%8d",a[i]);
}
printf("\n");
}
//バブルソート
void BubbleSort(int *a, int n) {
int i,j;
int s;
for (i=n-1; i>0; i--) {
for (j=0; j < i; j++) {
if (a[j]>a[j+1]) {
s = a[j];
a[j]= a[j+1];
a[j+1] = s;
}
}
}
}
//基本選択法
void Selection(int *a, int n) {
int i, j, i_max;
int s;
for (i=n-1; i>0; i--) {
i_max = 0;
for (j=1; j <= i; j++) {
if (a[j] > a[i_max]) i_max=j;
}
if (i_max != i) {
s = a[i];
a[i]= a[i_max];
a[i_max] = s;
}
}
}
//挿入法
void Insert(int *a, int n) {
int i, j;
int t;
for (i=1; i<n; i++) {
t=a[i];
for(j=i-1; j>=0 && a[j]>t; j--)
a[j+1]=a[j];
a[j+1]=t;
}
}
だけど、お前らのほとんどはM社の窓OSだから、M社のVisual Cとか、BorlandのCコンパイラーを使うことになるわな〜。窓OSのCコンパイラーで作った実行プログラムはEXEファイルが大きくなるし、なんたって、実行速度が死ぬほど遅い！！
この点はくれぐれも留意するにゃ。
だから、Windows版のgccをインストールしたほうがいいかもしれないにゃ。
バブルソート（泡立ち法） [数値解析]
バブルソート（泡立ち法）
いま仮に次のような数の列があるとする。
これを小さい数から大きい数へならぶ順（昇順）の数の列に変えたいとする。
この最もシンプルな方法は、隣り合う要素の大小関係を比較し、大小が逆転していたら、隣り合う２つの要素を交換するという方法。
具体的には、まず、｛３,2,1｝の（3,2）を比較する。３と２の大小関係が逆転しているので、３と２を交換し(2,3)にする。すると、
になる。
次に、｛２,3,１｝の（3,1）の大小関係を比較すると、順序が逆転しているので、３と１を交換し、（1,3）にする。
すると、
になる。
これで、最も大きい３を右端に並べられことができた。
ということで、｛２,1,３｝の部分列、部分集合
の要素を昇順に並べ替えればいいだろう。
（２,1）を比較すると、これは順序が逆転しているので順序を交換し、（1,2）にすると、
になる。
以上のことをまとめると、
と、隣り合う要素の大小関係を比較し、順序が逆転していたら両者を交換することによって、｛３,２,１｝を昇順に｛１,２,3｝にできる。
こういう数の列の並び替えをバブルソート（泡立ち法）という。
では、もっと複雑な
の場合について考える。
(4,2)は順序が逆転しているので、２つの要素を交換すると、
になる。
次に、（４,５）を比較すると、この順序は逆転していないので、交換せずにそのまま。
次に、（５,1）を比較すると、順序が逆転しているので、交換する。
次に、（５,３）を比較すると、順序が逆転しているので、２つの要素を交換する。
これで最も大きな５が右端に並べられた。
というわけで、今度は、
を同様に昇順に並べ替えればよい。
{2,4,1,3}→{2,4,1,3}→{2,1,4,3}→{2,1,3,4}
これで、最大の４を右端に持ってくることができたので、４を取り除いた部分集合
{2,1,3}
を同様に並び替えると、
{2,1,3}→{1,2,3}→{1,2,3}
になる。
これですべて昇順に並び替えることができたのだけれど、{1,2,3}の最大値３を取り除いた部分集合
{1,2}
を昇順に並び替える。
{1,2}→{1,2}
これで並び替えの作業はおしまい。
これで、{2,4,5,1,3}を昇順に{1,2,3,4,5}と並び替えることができた。
さらに一般的につぎのような数の列、集合があるとする。
これを昇順に並び替える方法、アルゴリズムは次のようなものになるだろう。
do i=n、n−1,n−2、・・・,2
do j=1,2,・・・,i−1
a(j)とa(j+1)の大小を比較してa(j)とa(j+1)を交換
end do j
end do i
フォートラン的な記述ですが・・・。
これを元にFortranのプログラムを作ると、次のようになる。
! バブルソート
parameter(n=5)
integer a(n)
integer dummy
a(1)=4; a(2)=2; a(3) = 5; a(4)=1; a(5)=3
do i=n, 2, -1
do j=1,i-1
if (a(j).gt.a(j+1)) then !順序が逆転していたら交換
dummy = a(j)
a(j)=a(j+1)
a(j+1)=dummy
end if
end do
end do
write(*,*) a
end
バブルソートを用いると、昇順にデータを並び替えられるのですが、この方法は、データの比較・交換の回数が最悪、
約n²/2回。
n=100ならば最悪5000回、n=1000ならば５０万回、n=1万ならば５千万回と、データの数nが大きくなると、データの比較・交換回数が大きくなりすぎるので、実際の並び替え、ソーティングでバブルソートが使われることはない。
まぁ、パソコンといえども、現在は処理速度、計算速度がトンデモなく速いから、データ数が１万くらいあってもバブルソートですぐに並び終えるので、データ数が１万くらいまでならば、最も基本的なバブルソートで十分に実用に足りると思うけれど、コンピュータの能力が低かったときは、バブルソートの遅さは致命的だったんだケロよ。
次回は、バブルソートよりも少しだけ早くソーティングが可能になる方法を紹介するにゃ。
