* アルゴリズムとデータ構造 [#p8c4a8bb]
この頁の解説貧弱すぎｗｗなめてんだろｗｗｗ~
と思った奴は何か書いてくれ
#contents
* 計算量 [#p6073ad2]
アルゴリズムがどれだけ効率的かを示す概念が''計算量''です。通常、単に計算量と述べた場合は、データ数nに対してどれだけ時間がかかるかを示す''時間計算量''を指しますが、場合によってはどれだけメモリを消費するかを示す''空間計算量''を問題にするケースもあります。計算量は、通常データ数nが十分大きい場合にnのどういう関数に比例して計算時間／メモリ消費が増えるかという形式で表します。
具体的に、下に述べている[[線形探索>#oc5e463b]]の例で計算量を考えてみましょう。この関数では、ループをサイズn回だけ回していますが、このループ1回辺り時間tだけかかるとしましょう。さらに、関数の呼び出し等により、データ数にかかわらず一定の時間sがかかると考えられます。従ってこの関数に費やす時間はnt+sですね。この時、十分大きいnを考え、かつ定数倍は無視して考えます。例えばntがsの10000倍だと仮定しましょう。この時sの寄与は、体重計に載るときに体についているホコリみたいなもので、無視できますね。更に計算量を考える際には定数倍のtは無視するので、結局線形探索の計算量はデータ数nに比例しています。これを''O(n)''と書き、''オーダーn''と読みます。
一般に、計算量がデータ数によらない定数（O(1)と書きます）のアルゴリズムは極めて優秀です。また、nが極めて大きい時は、log nは定数に毛が生えたくらいだと思って構いません。データ数が1000から10000に一桁上がっても、計算時間はlog10の定数倍でしか増えないのですから。なので、計算量がO(log n)のアルゴリズムもかなり優秀です。計算量がO(n)のアルゴリズムは、まあ普通。前述の理由から、O(n log n)のアルゴリズムも同様です。計算量がO(n^2)になると、ちょっとしんどい。データ数が10倍になると、計算時間が100倍になるわけです。計算量が指数関数で表されるアルゴリズムは、はっきり言って実用にはなりません。
なお、このような記法はあくまでnが大きい時に重要になるのであって、十分小さいnではO(n^2)のアルゴリズムの方がO(n log n)より速いということも十分起こりえます。実際、ソートを行うときは最初はO(n log n)のクイックソートを使って、個数が数個になった状態でより速いO(n^2)の選択ソートに移行するというのが定石です。
* アルゴリズム [#v958b98c]
問題を解くための手順を''アルゴリズム''と呼ぶ。~
但し、アルゴリズムと呼ばれるためには以下の条件を満たさなければならない。
・問題を解く上で正しいこと。
・手順が具体的に示されていること。
つまり、コンピュータで実行可能なように、曖昧さがなく記述されていること。
・有限の実行時間で、必ず終了すること。
** 探索 [#i297b629]
*** 線形探索 [#oc5e463b]
英語ではリニアサーチ。~
何のひねりもなく、先頭から末尾まで探していくだけのサーチです。~
データが多くなると遅くなりがちですが、何の前提条件も無く使える手軽さが利点です。~
シンプルなので、要素の数が10個前後の小規模な配列に対してはかえって高速だったりします。~
例:C言語(配列のアドレスとサイズを渡し、numと一致する要素の添字を返す)~
int linear_search(int *array, unsigned int size, int num){
int i;
for(i = 0; i < size; i++){
if(array[i] == num) return i;
}
return -1;
}
配列の要素数が増えれば増えただけ探索に時間がかかるようになります。~
要素数10000の配列は、要素数10の配列の1000倍時間がかかるわけです。~
このように、データ量と処理時間が単純に比例して増える事を「線形時間」とかO(n)とか表現したりします。~
１番時間がかかるのは探しているデータが存在しない場合で、１番時間がかからないのは、先頭にあった場合です。~
*** 二分探索 [#qce356fb]
英語ではバイナリサーチ。~
整列済みの要素群に対して実行します。 性質上、再帰を用いて実装される場合が多いです。~
例:C言語(配列のアドレスとサイズを渡し、numと一致する要素の添字を返す。配列はbegin側が小さい値になる順で並んでる)
int binarysearch(int * array , unsigned int size , int num) {
int begin = 0; int end = size - 1; int center;
while(1) { //無限ループ
center = (begin + end) / 2;
if(array[center] >= num) { //numは中間より前にある（もしくは一致している
if(array[center] == num) { return center; } //←発見！
end = center - 1;
}
else { //numは中間より後にある
begin = center + 1;
}
if(begin > end) return -1; //探す範囲が無くなってしまった
}
}
整列の中央と探索対象を比較すると、その結果で整列の
左側あるいは右側だけに候補を絞ることができます。~
そして、その搾られた候補に対して同じ要領で中央の値との比較と候補の絞り込みを繰り返していくと~
いずれある時の中央の値あるいはただひとつに絞られた候補として
探索対象が現れます(整列に探索対象があれば)
要素数１の時の処理時間を基準にすると、要素数４でも３倍、８でも４倍、１６でも５倍……みたいな感じで増加が緩やかです。~
１回の比較で、探索候補の半分を振るい落とせるためです。~
このように、データ量が倍に増えても処理時間は緩やかにしか増えない事を「対数時間」とかO(log n)とか表現したりします。
線形探索のO(n)と比べるとデータ量の増加に強いものの、処理が少々複雑なため~
要素が少ないうちは線形探索よりも遅かったりしますが、総合的にはこちらの方が断然速いと言えます。
** 整列 [#h84db045]
*** ボゴソート [#h92fd60b]
世間にはあまり知られておらず、専門書にもまず載っていないが、~
他のソートアルゴリズムに比べ極めて分かり易いアルゴリズムであり、~
訓練をすれば猿はおろか犬でも習得できる。~
要素をランダムに並べ替え、順番に並んでるかを確認し、もう一度ランダムに並べ替える。~
この操作をソートが完了するまで行う。~
運がよかったら一発で終了するがそうでない場面の方が圧倒的に多く、乱数によっては永遠に終わらない可能性もある。~
ソートが終了するかかどうかは「無限の猿定理」でぐぐると幸せになれるかも。~
~
所謂ツンデレソート。「一回で終わるわよこんなソート！」~
一回で終わったためしがなく、バブルソートよりはるかに遅い。~
計算時間はO(n*n!)~
void swap(int* p1, int* p2)
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
void bogo_sort(int* array, int size)
{
srand((unsigned)time(NULL));
int i;
while(1){
int sort_flag = 0;
for(i = 0; i < size-1; i++){
if(array[i] > array[i+1]){
sort_flag = 1;
}
}
if(sort_flag){
int t1 = rand()%size;
int t2 = rand()%size;
swap(&array[t1], &array[t2]);
}
else{
return;
}
}
}
~
***バブルソート [#c164d24f]
初心者の坊や達を優しくソートの世界に導いてくれる方。~
とても素直だけど、遅いので実戦の場に出ず教育者として活躍しています。
例:C言語
void bubble_sort(int *array, unsigned int size){
int i, j, t;
for(i = 0; i < size; i++){
for(j = size - 1; j > i; j--){
if (array[j] < array[j - 1]){
t = array[j];
array[j] = array[j - 1];
array[j - 1] = t;
}
}
}
}
隣り合ってる要素を比べて、並べたい順番になってなかったら入れ替える、という操作を繰り返すわけです。~
要素が正しい位置に泡のように登っていくのでバブルソートと名付けられました。~
単純ですが無駄な比較が多く、遅いです。
サンプルコードを見れば分かるように、ループを二重に回しています。この回数が計n(n-1)/2回。なので計算量はO(n^2)と、ちょっと辛いです。
***シェーカーソート [#eaad47d0]
バブルソートの親戚。~
挟みこむような動きで少しだけ無駄を減らす事に成功しました。~
カクテルソート等とも呼ばれます。 オシャレですね。~
バブルソートで走査中、最後に入れ替えがあった位置よりも後ろは、綺麗に並んでる事がわかります。~
つまり、最後に入れ替えがあった位置を記録し、次からはそれ以降を無視すれば少し無駄が少なくなるわけです。~
そこで更に、前方後方と交互に走査すれば、両方から範囲を狭める事が出来るので少しだけ効率が良くなるのです。~
%%ぶっちゃけ大して変わらないとか言うな。%%
実際計算量もO(n^2)。
***コムソート [#d6da5661]
バブルソートの親戚。~
色々な大きさの櫛を駆使します。~
隣同士ではなく、まず適当に大きな間隔を開けて比較・交換をします。~
どんどん間隔を小さくしていきつつ走査を繰り返し、最後は間隔が無くなり、隣同士を交換するようになります。~
この隣同士の交換が終わった時、既にちゃんと整列出来てしまっています。~
ずっと細かく見ていくよりも、最初は大雑把にやった方が効率が良いという事らしいです。~
飛び飛びに揃えていくのが髪をとかす櫛（コム）のように見えるからこの名前がつきました。~
計算量は理論的にはO(n^2)のはずですが、実験的にO(n log n)の速度が出ることが知られています。なお、このソートは[[不安定>#h37e2e26]]です。
***挿入ソート [#b78ed62f]
手当たり次第に突っ込む単純な子ですが、状況次第ではなかなかの速さ。~
大変に開放的な性格です。~
例:C言語~
void insertion_sort(int *array, unsigned int size){
for (i = 1; i <size ; i++) {
for (j = i; j > 0 && array[j-1] > array[j] ; j--)
{swap(data[j-1] , data[j]); } //要素の交換
}
前から順に見ていき、要素を正しい位置に挿入していきます。~
この「挿入」の操作そのものは、バブルソートと同じような要領です。離れた位置に挿入する程、比較や交換の回数が多くなります。~
動きとしては、配列の前部に 整列したデータがどんどん溜まっていくような感じです。~
ほとんど整列済みのデータなら離れた所まで挿入する事が少なくなるので、かなり高速になります。
計算量はO(n^2)ですが、そのような性質から、O(n log n)のソートの、最後数個だけになった状態を選択ソートを使って行うことがあります。
*** シェルソート [#ua3da88b]
挿入ソートの親戚。~
やはり突っ込むばかりだけれど、少しずつ間隔を開けたりする賢さがあります。~
別に貝殻が好きというわけではなく、Shellさんが開発しただけだったりする。~
挿入ソートとシェルソートの関係は、バブルソートとコムソートのようなもので~
「最初は大雑把にやって、最後だけ細かく仕上げた方が効率が良い」という事を利用しています。~
具体的には、ある程度の間隔を開けて挿入ソートを行い、どんどん間隔を狭くしていくのです。
*** 選択ソート [#t69c50e9]
馬鹿ソートとか言われたりするけど気にしない明るい子。~
とりあえず一番小さいのを探し続ければそのうち揃うよね！
配列を走査し、最も小さい(ソート後に端に来る)データを見つけてから、それを１番最初のデータと交換します。~
そして、２番目の小さいデータ、３番目に小さいデータ、と次々に処理していきます。~
最後の１個を見るまで「一番小さい」かどうかはわからないため、結局全部見ていく事になり、大して効率は良くありません。~
交換回数は少ないため、バブルソートよりは高速と言えます。
でも計算量はO(n^2)。
*** クイックソート [#h788cb12]
最速の名をほしいままにしているが、たまにさぼっちゃう気まぐれ屋さん~
スレンダーな子です~
複雑と思われがちですが、実は意外と単純です。~
まず配列からある要素A（''ピボット''といいます）を取り出して、それぞれの要素がAより小さいければ前、大きければ後、と振り分けます。~
次にAより前に振り分けられた部分からまた、ある要素Bを取り出して、Aより前に振り分けられた部分の中で、Bより小さければ前、大きければ後、と振り分けて行きます。 ~
このようにある要素をピボットとして取り出し、それを基準として前後に振り分けて行くのがクイックソートです。
計算量は分割の回数が大体O(log n)、各ステップ毎にO(n)かかるので、O(n log n)と、優秀なアルゴリズムです。が、ピボットの選択を間違えるとかなり悲惨。例えば、ピボットを配列の振り分けられた部分の最後の要素に選ぶとしましょう。そして、既にソートが完了しているデータをクイックソートに突っ込むとしましょう。この時、一番最後の要素は一番大きいので、全てのデータがピボットより前に振り分けられます。そのあと、そのなかから一番大きい要素（＝全体で2番目）をピボットとして選び、残り全部がそれより前に振り分けられます。……これって、バブルソートとほとんど一緒ですね。結局分割回数がO(n)だけかかってるわけですから。なので、クイックソートは''平均計算量''がO(n log n)、''最悪計算量''がO(n^2)という言い方をします。
このように効率の悪いピボットを選ぶ可能性を排除するため、配列から3つほどデータを取り出して、その中央値をピボットに選ぶということが通常行われます。また、要素が10個くらいであればクイックソートよりも選択ソートの方が速いので、ある程度まで分割が小さくなったら以降は選択ソートに切り替えると速くなります。
クイックソートの重要な欠点としては、他に不安定であることがあげられますね。
void sort(int*a,int s){
int i=-1,j=s,p=a[s/2],t;
for(;;){
while(a[++i]<p);
while(a[--j]>p);
if(i>=j)break;
t=a[i];
a[i]=a[j];
a[j]=t;
}
if(0<i-1)sort(a,i);
if(j+1<s)sort(a+j+1,s-j-1);
}
*** マージソート [#y34cbfeb]
いつも手を抜くことなく、速さを常に追求する努力家~
クイックソートには負け越しているのをくやしがっている~
他の子より大きいのが悩み~
まず、配列を真っ二つに分けます。 分かれて出来た２つの配列を、更にそれぞれ真っ二つにします。~
これを繰り返し、完全にバラバラになってしまうまで分割してしまいます。~
分割が終わったら、今度は逆にマージ(合併)していきます。 この時、上手く順番に並ぶようにマージします。~
マージして出来た配列を更にマージしていって、最後にたった１つの配列になった時、ソートが完了しています。~
綺麗に並んだ配列２つをマージする時は、それぞれの配列の「端だけ」比較すればいいので比較回数が少なくて済むのがポイント。~
（１，４，５）と（２，３，６）なら、まず左端の１と２だけを、次は４と２だけを……という風に。~
マージにO(n)の余分なメモリ領域が必要な事と、平均するとクイックソートより僅かに遅いのが難ですが、かなり速いソートの１つです。
それだけじゃクイックソート使えばいいじゃないかとなりますが、こちらは速度が安定しています。~
外部記憶が必要なくらい大きなソートをする場合クイックソートよりもこちらを使うことのほうが多いです。~
また、安定ソートでもあります。 なんとなく堅牢なイメージがありますね。
*** ヒープソート [#l50b875a]
[[ヒープ>#v35e1d11]]構造を利用したソート。計算量はO(n log n)なのですが、メモリのアクセスが連続していないせいでクイックソート・マージソートよりも通常遅くなります。おまけに安定でもない。じゃあこのソート、どういう時に使われるかというと、思い出して欲しいのがクイックソートの欠点。クイックソートは分割回数が多くなると極めて効率が悪くなるのでした。そのようなデータを入力としてよこされた際には、分割回数が一定以上を越えるとアルゴリズムをヒープソートに切り替えます。このようなソートを''イントロソート''と読んだりもします。これで、O(n^2)の時間が必要になる事態を避けようというわけです。
*** バケットソート [#b490822c]
他にもビンソートとか色々あだ名がある。~
趣味で大量にバケツを集めすぎて家を崩壊させてしまうような性格のせいで~
秘めたポテンシャルを発揮出来ずにいる。
「０～１００点のテストの点数をソートするんなら、１０１個のバケツを並べてぶちこんで順に取りだしゃいいじゃん！」~
という事をマジでやるというトンでもなく豪快なソートです。~
比較と入れ替えを繰り返すものが多いソートの中で、非常に独特な性質を持っています。
まず、データがいくら増えようと「バケツに入れる」という操作の回数が単に増えていくだけなので、なかなか重くなりません。~
（データ量が千倍になればクイックソートでも大体１万倍重くなりますが、バケットソートは、単に千倍です）~
非常に速いソートですが、当然弱点があり「バケツを用意するために大量のメモリが必要」なのです。~
例に出した0～100の範囲ならまだいいのですが、32bitのint型で表現出来る全ての数をソートしようとしたなら~
範囲は-2,147,483,648～2,147,483,647という事で、4294967296個のバケツが必要になります。~
また、ソートしたいデータに同じ数値が重複してる場合があります(テストで同じ70点を取った子が何人もいたとか)から~
バケツは単純な配列として用意する事は出来ません。配列には１つのデータしか入れられないのです。~
大抵はリンクリストの配列みたいな実装になるのですが、リンクリストにも余分なメモリが必要なので更に酷くなります。
このように、使うための条件は厳しいものの、計算量は通常の比較ソートでは不可能なO(n)を実現しているため、クイックソートよりも高速に処理出来たりなどロマンが溢れるソートです。
*** 分布数えソート [#r779f37a]
バケットソートの親戚。~
一応バケットソートよりはマシなものの、やはり家が崩壊しがち。
バケットソートはリンクリストを使った実装だと 動的なメモリの確保や条件分岐が頻繁に起こり、折角の速度が出せません。~
なので、もっと上手い方法は無いのか、という事で考え出されたものがこれです。
まず、以下のようなデータがあったとします。
0 1 2 0 0 3 1 2 0 2 2 0
これを昇順にソートすると
0 0 0 0 0 1 1 2 2 2 2 3
このようになるわけですが、最も左を「0番目」として数えると~
0は0番目から、1は「0の個数(5)」である5番目から、2は「0の個数(5)＋1の個数(2)」である7番目から~
3は「0の個数(5)＋1の個数(2)+2の個数(4)」である11番目から始まっている事がわかります。
これを利用し「何番目から始まるか」という数だけをバケツに入れれば、リストでなく単なる配列で実装でき~
同じ数値が重複してても、その要素を処理するたびに「何番目から始まるか」のバケツを＋１していくだけで対処出来ます。~
このような実装をすれば リンクリストのための余分なメモリも、その確保にかかる時間も、分岐も、少なく済むため高速なのです。~
ただし、要素の数を数えるための走査と 実際にソートをするための走査で、合計２回の走査が必要になるため~
ソートしようとしているデータの規模によってはかえって低速かもしれません。~
(リンクリスト用のメモリの動的確保や分岐は結構重いので、測ってみると大抵はこちらの方式の方が速かったりしますが)
*** 基数ソート [#od200194]
バケットソートの友人。 英語にするとラディックスソート。~
極限られた状況でのみ他を圧倒する速さを出す可能性を秘めている~
しかし、あまり活躍の機会がないのでたまに忘れ去られてたりする。
基数というのは数を表す際に基本となるまとまりの事で、例えば「○進数」の○の部分です。~
１桁目、２桁目、３桁目のように桁ごとにソートしても、順番さえ保存されてれば上手い事揃う、という事を利用するソートです。
以下のようなデータがあったとします。
19 70 35 48 24 14 40
これを１桁目だけに注目して、小さい方を左に来るようにソートすると
70 40 14 24 35 48 19
更に、この順番をなるべく保ったまま２桁目だけに注目してソートすると
14 19 24 35 40 48 70
このように、結果的に綺麗に揃っており、これは3桁に増えようと、10進数でなかろうと適用出来ます。
例えば、バケットソートで0～9999の範囲を整列せねばならなくなった場合、本来なら10000個のバケツを用意するわけですが~
これを利用して「下２桁を基準にソート→上２桁を基準にソート」とすれば、なんと100個のバケツで済むわけです。~
当然、分けただけソートの回数は増えますし、分ける事そのものにいくらか時間がかかりますので(割り算したり剰余を取ったり)~
バケットソートほどの速度は出ないのですが、それでも十分速かったりします。~
速度を求めるなら割り算や剰余ではなく、CPU的にキリの良い２のべき乗で区切ってシフトやマスクを駆使すればなお良し。
「桁ごとに区切っても揃う」という原理は別にバケットソートでなくても通用するのですが~
その他のソートだと単に処理の回数を増やすだけで何の利点も無いので、大抵バケットソートの改良版として紹介されます。~
「バケットソートは超速いけど、メモリ喰いすぎるのがちょっと……」という方にお勧め。~
範囲さえある程度絞れるならクイックソートよりも普通に高速に実装出来ます。~
工夫次第で負の数を含んでたり浮動小数を扱ったりする場合にも対応出来ます。
*** 逆写像ソート [#pfbe4b79]
バケットソートの親戚。~
一見、数学的で難解な事を考えていそうな雰囲気ですが、割と豪快な性格です。
写像とは小難しそうな数学用語ですが、「２つの数字の集まりを対応させる」というだけの単純な概念です。~
添字を入れると要素が出てくる配列も 添字→要素の写像と言えます。~
「逆写像」というと、その逆になり、要素→添字という写像になるわけですが~
そういう配列＝バケツと考えると、実の所それはただのバケットソートという事になります。
バケットソートとの違いは「値が同じ要素があった時の対処」の部分だけで、事実上それだけが逆写像ソートのアイデンティティです。~
その対処の仕方とは「添字をポインタ代わりに使ってリンクリストのようなものを作る」というもので~
リンクリストでいう next に対応する添字の値を確保するため、ソートする配列と同じサイズのnextの配列を用意するのです。~
この配列のおかげで、バケツに１つの要素しか入れる必要が無くなっているのがポイント。~
ぶっちゃけバケットソートや分布数えソートを使えば済むので、知ってる人すら少ないマニアックなソートです。
*** 奇遇転置ソート [#f9f10dce]
バブルソートの親戚。~
チームプレーや流れ作業が得意な方。
バブルソートは隣合った要素を比較、交換していくので~
「１ ２」「２ ３」「３ ４」を添字として処理していくわけですが~
奇遇転置ソートは「１ ２」「３ ４」「５ ６」のような「奇数 偶数」要素を処理と~
「２ ３」「４ ５」「６ ７」のような「偶数 奇数」要素の処理を交互に行う、というような動きをします。
処理の回数そのものはバブルソートと大して変わらないのですが~
ポイントは「１ ２」「２ ３」 だと「２」が かぶってますが「１ ２」「３ ４」だと何もカブらない、という点です。~
つまり１回１回の処理が独立しているため、複数のCPUを使って並列に処理しやすいのです。~
いくら大量にCPUがあっても、走っているスレッドが１つだけなら１個分の性能しか出せません。~
CPUを増やせば増やしただけ速く出来るという限界の高さに並列処理の価値があるわけです。
逆に言えば、並列処理が出来る環境でなければ大して役に立たないソートです。
*** シェアソート [#ya8737c6]
共有のソート。~
部下を団結させ、隊列を整えるチームワークを発揮させるやり手の指揮官です。~
一次元の住人が多いソート業界では珍しい二次元の世界の住人です。
まずは、要素数[30]の配列→[6][5]の二次元配列、みたいな感じに分割します。~
そして１行目[1][i] ２行目[2][i] ３行目[3][i]……のように各行別々にソートするのと~
１列目[i][1] ２列目[i][2]……のように各列別々にソートするのを交互に行っていきます。~
各行や列は、それぞれ独立しているので、並列に処理が出来ます。~
「奇数行は左が小さくなるように、偶数行は、右が小さくなるようにソート」~
「列は、上が小さくなるようにソート」~
これを交互に繰り返す事で、小さい値は左右にクネクネ動きながら上に登っていきます。かなりトリッキー。
ちなみに、各行に対して行うソートは何を使ってもいいですが~
奇遇転置ソートやマージソート等を使うと並列性を更に上げられるでしょう。~
複数のCPUを搭載している状態なら、かなりの速度向上が期待出来ます。~
もちろん、並列処理が出来る環境でなければ、さほどのスピードは出ません。
*** バイトニックソート [#ud51908c]
究極のスピードを誇っているものの、力を出しすぎると地球が吹き飛ぶため本気を出せない。~
が・・・あ・・・離れろ・・・死にたくなかったら早く俺から離れろ！！~
理論上最高の速度が出るソートですが、やってる事は凄く単純で~
if や else等の分岐を大量に使って最小限の回数の比較、交換しかしない、というだけのものだったりします。~
性質上、ソートする配列のサイズがわかってて、しかも極端に要素が少ないものにしか使えません。~
要素の数が４つだけの場合でも使うifやelseの数は数十個に及び、６つを超えたあたりで百を超えます。~
書くのが異様に面倒なので、実際に使いたいなら そういうコードを生成するジェネレータを作りましょう。~
また、当然実行ファイルのサイズも爆発的に増えていきます。 ~
何億回もソートを繰り返すような処理が必要でなければコストに見合ったリターンは得られないソートです。
※どうやら上記のソートは本来の(？)バイ・トニックソートとは違うもののようです。~
本格的なバイ・トニックソートは、むしろマージソートに近く、並列処理なんかに使われるものなんだとか。~
正確な情報はちょっと持ってないので、知ってる人は編集してくだしあ＞＜
*** 安定ソートと、そうでないソート [#h37e2e26]
等価なデータの順番がソート前と同じという事が保証されているソートの事を「安定ソート」と呼びます。~
言葉にすると難しいですので例を出しましょう。
例えば、このようなデータがあるとします。~
データ 「A：50」「B：20」「C：80」「D：20」「E：60」
これを「数字だけを基準に、小さい方が左に来るようにソート」すると
結果１ 「B：20」「D：20」「A：50」「E：60」「C：80」
結果２ 「D：20」「B：20」「A：50」「E：60」「C：80」
このどちらかになる事が予想出来ますが~
安定ソートだと「元々Bの方が左にあった」という事で、必ず結果１になります。~
クイックソート等の安定でないソートを用いると、結果１になるか結果２になるかは全くわかりません。~
「そんなのどうでもいいから速いほうがいいよ」という場合にクイックソートを使い、順番が重要な時は安定なソートを使うわけです。
多くのソートが安定ですが~
コムソート シェルソートなどの間隔を開けて処理をするソートや~
クイックソート等は、安定でないソートとして知られています。
安定と言われているソートでも、実装の仕方によっては安定でなくす事も出来てしまいますが~
あえて安定にしない事で得するような事はあまり無いです。~
また、基数ソートのように安定なバケットソートを利用しないと実現出来ないものもあります。
** 最短経路問題 [#lf212c0c]
*** ワーシャル・フロイト法 [#f8c41450]
こいつはなぁ、全通り調べるんだよ
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
for(k = 0; k < n; k++){
if(array[j][k] > array[j][i]+array[i][k]){
array[j][k] = array[j][i]+array[i][k];
}
}
}
}
jからkに行くまでのコストについて比較してる
j→kとj→i→kっていくのがどっちが安いのか
こうすると自然に最短経路が埋まる
3重ループは全通り調べられるから他のアルゴリズムにも使える
このアルゴリズムは要素が多いときは不向き
*** ダイクストラ法 [#l7e4f36c]
ダイクストラとは、かの有名な論文''"Go To Statement Considered Harmful"''を発表して構造化プログラミングを提唱した人物なのだ。
難しそうに見えて実は簡単・・・じゃないか
じゃあこの問題があったとしよう
夏休みにニートのvipeerは旅行に行こうとしましたが働いていないのでお金がありませんでした。
親から金をもらいに行く勇気のなかったvipperは極力少ないお金で目的地に行こうとしました。
ここで出発地から目的地まで行く最低のコストを求めよ
また、要素の数nは10まで、nが入力されたあとa b cが入力され、それぞれaからbまで行くお金cが入力されます。
最後の行にs,gは入力されsは出発地、gは目的地である。
またbからaにも同じだけの値段がかかるとし、a,bはnまでの数で0からn-1までのおおきさである。
こんなもんワーシャルフロイドでやれや(笑)って言わないでね
入力のところは
#include<stdio.h>
#define MAX (10)
int main(void)
{
int n;
int a, b, c;
int i;
int cost[MAX][MAX]; // それぞれの場所までの値段
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
cost[a][b] = c; // aからbに行くまでの値段
cost[b][a] = c; // bからaに行くまでの値段
}
return 0;
}
これが基本
ここからダイクストラを実装すると
for(i = 0; i < n; i++){
used[i] = 0; // すべて使っていないことにする
val[i] = INT_MAX; // すべてのコストを最大にする
}
val[s] = 0; // 出発地のコストは0
while(1){
minVal = INT_MAX;
for(i = 0; i < n; i++){
// 確認してないで 一番安い出発地からのコストが一番安いところを探す
if(used[i] == 0 && val[i] < minVal){
minVal = val[i];
min = i;
}
}
// もしすべて確認が終わったとき終了する
if(minVal == INT_MAX){
break;
}
used[min] = 1; // 使用済みにする
for(i = 0; i < n; i++){
// minからiにいけてかつ最小コストの時更新
if(cost[min][i] && cost[min][i] + val[min] < val[i]){
// minからiまで行く値段と出発地からminにくるまでの値段を足す
val[i] = cost[min][i] + val[min];
}
}
}
こうなる
時間がないからまた今度書く
全体は
#include<stdio.h>
#include<limits.h>
#define MAX (10)
int main(void)
{
int n;
int a, b, c;
int s, g;
int i, j;
int cost[MAX][MAX]; // それぞれの場所までの値段
int used[MAX]; // 確認済かどうかのフラグ
int val[MAX]; // 出発地からのコスト
int minVal, min;
scanf("%d", &n);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
cost[i][j] = 0; // 初期化しておく
}
}
for(i = 0; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
cost[a][b] = c; // aからbに行くまでの値段
cost[b][a] = c; // bからaに行くまでの値段
}
scanf("%d %d", &s, &g);
for(i = 0; i < n; i++){
used[i] = 0; // すべて使っていないことにする
val[i] = INT_MAX; // すべてのコストを最大にする
}
val[s] = 0; // 出発地のコストは0
while(1){
minVal = INT_MAX;
for(i = 0; i < n; i++){
// 確認してないで 一番安い出発地からのコストが一番安いところを探す
if(used[i] == 0 && val[i] < minVal){
minVal = val[i];
min = i;
}
}
// もしすべて確認が終わったとき終了する
if(minVal == INT_MAX){
break;
}
used[min] = 1; // 使用済みにする
for(i = 0; i < n; i++){
// minからiにいけてかつ最小コストの時更新
if(cost[min][i] && cost[min][i] + val[min] < val[i]){
// minからiまで行く値段と出発地からminにくるまでの値段を足す
val[i] = cost[min][i] + val[min];
}
}
}
printf("%d\n", val[g]);
return 0;
}
*** A* [#g531e457]
A*と書いて「エースター」と読む。~
ダイクストラ法は「出発地から経由地までのコスト」が最小となるように経路を選択するのに対し、~
A*はこれに加えて「経由地から目的地までのコスト」も参照する。~
そして、それぞれのコストの和が最小となるように次の経由地を選ぶアルゴリズムだ。
ただし、このアルゴリズムの適用にあたって注意がある。~
それぞれの経由地から目的地までのコストが分かっていないといけない。~
と言っても、正確なコストはこれから調べるんだから分かるわけがない。~
そこで、「たぶんこれくらいのコストだろう」という値を用いる。~
この時のコストの見積もりは、実際のコストより「必ず」低く見積ること。~
証明は省略するが、最短経路を求める条件として必要だからだ。~
そのような見積りとしては、例えば目的地までの直線距離なんかがある。
** 動的計画法 [#se794f0d]
* データ構造 [#wc0c038f]
** 配列 [#p0a42e9d]
気にしたことないだろうけど、配列も立派なデータ構造なんだぜ。~
重要なことは、多くの言語やその処理系でO(1)のアクセススピードが保証されてるってこと。~
つまり、ほかのデータ構造に比べて単純な分、早いんだなこれが。~
馬鹿とはさみは使いようってやつだな。
** スタック [#e04037cc]
お菓子でいうとPEZ(ペッツ)
「干し草の山」の意。~
名前の通り、新しいデータを上に積み上げていき、下に埋もれた古いデータを取り出すためには~
上のデータを先に取り出さなければならない後入先出(あといれさきだし)の構造です。~
「古いデータは取っておき、新しいデータに対して色々な処理をしてから利用する」ような場面で使われます。~
例えば関数・メソッドの呼び出しの際に使われるコールスタックなんかが有名。~
ローカル変数は他の関数を呼び出してから戻ってくるまでずっと保存されてますが、それはスタック上にあるからなのです。
** キュー [#x9b212e8]
ところてんだよところてん
「待ち行列」の意。
名前の通り、古いデータは新しいデータの後ろに並び、新しいデータが出て行くまで取り出せません。~
先入先出(さきいれさきだし)の構造です。~
「先のデータの処理が終わるまで、後から来たデータにちょっと待ってもらう」ような場面で使われます。~
サーバーなんかは、すぐに処理出来ない大量のリクエストが来た場合のためのキューを持っているのが普通です。~
(優先度が高いリクエストはキューで待たせず割り込ませてあげるような機能もありがちです)~
mallocとか使わないクズキュー~
#define QMAX 100
typedef struct{
int que[QMAX];
int hp,tp;
}queue;
void init(queue* q)
{
q->hp = 0;
q->tp = 0;
}
int isempty(queue q)
{
return q.hp==q.tp;
}
void push(queue* q,int n)
{
q->que[q->tp++]=n;
if(q->tp==QMAX)q->tp=0;
}
int pop(queue* q)
{
int res=q->que[q->hp++];
if(q->hp==QMAX)q->hp=0;
return res;
}
こんな感じで使う~
http://ideone.com/Dt13X
** デック [#gffe4778]
Deque。 スタックとキューを合わせたような機能を持っています。~
具体的には「前から入れる」「前から出す」「後から入れる」「後から出す」の全てが出来ます。~
長所：両端へのデータ挿入がO(1) 添字アクセス可能~
短所：要素の中央の挿入、削除が遅い
削除、挿入は平均すると動的配列より優れるが、単純なアクセスではやや劣る。
** リスト [#n30cdd26]
連結リストとも呼ばれる非常に一般的なデータ構造の一種。~
ある箱を仮想的に考え、それと別のはことをつなぐようなイメージのデータ構造。~
箱は変数を表すと考えれば、箱同士のつなぎ方によっていくつかの種類に分かれる。~
多くの言語では、箱と連結部分を一括して扱うために、構造体などを用いる。~
最近のモダンな言語ではライブラリにリスト構造があらかじめ用意されている場合が多い。~
また、Lispなど「リスト構造ありき」で言語設計がなされているプログラム言語も少数ながら存在する。~
似たようなデータ構造に配列が存在するが、N番目の要素にアクセスする時に必要な計算時間が、配列ではO(1)なのに対して、リストではO(N)かかるという点が大きく異なる。
従って、使用できるメモリーの割合や扱うデータの特性によっては、リストよりも配列を利用したほうが有効な場合もある。
リストが有利なのは、極めてデータ数が大きい際に、頻繁に途中へデータを挿入／削除する場合。配列やデックでは基本的に残りのデータをずらすことになるので、計算量O(N)かかりますが、リストでは位置の特定さえ出来ていればあとは箱を繋ぎ変えるだけなのでO(1)でできちゃいます。
*** 単方向リスト [#c3b02503]
リストの要素同士を連結するとき、A→B→C→……のように、一方向のみの連結を利用する方法。~
このとき、例えばある要素を検索したい場合、現在の位置をAとすれば、Cを参照しするには、A→B→Cと順にたどっていけばいいが、現在の位置をCとしてBを検索するときにも、いったん現在位置をAに戻して、先頭から検索しなければならないという手間が生じる。（C→B→Aのように、逆順にはたどれない）~
通常、リストといえばこちらを指す。~
一方向への連結しかみないので管理が楽で、使用する領域も少なくて済み、デットリンク（リストの途中で無意味な場所を指している連結部分）を探すのも楽。~
電話帳のように、前の要素に戻る必要が生じにくいデータの表現に適している。
*** 双方向リスト [#sf7d12f5]
単方向リストと異なり、逆順にも辿れるようにしたリスト。~
単方向リスト同様、矢印表記を用いれば、A⇋B⇋C⇋D⇋……と表すことができる。~
特徴は、ある要素Nへのアクセスオーダが必ずしもO(N)にならないことで、検索開始位置を現在の要素とすることで、O(N-現在の要素位置)の関係で要素にアクセスできる。~
現在位置を覚えておきつつ、前後の要素にアクセスするようなデータの表現に適している。
*** 循環リスト [#wbdee299]
上記二つのリストのどちらとも併用できる連結方法で、リストの末尾の次の要素を、リストの先頭につなぐリストの作り方を言う。~
通常、リストの末尾の次の要素は、NULL等の末端であることを明確に示すシンボルを指しているが、循環リストでは末尾が無くなるので、ある要素の次の要素に必ずアクセスできるようになる。~
例えば、あるデータを検索するときに、末尾まで検索したら先頭要素から検索しなおすような場合、通常のリストでは末端に来た時には先頭に戻るような処理を書き加える必要があるが、循環リストではどのような場合に終了させるかを記述するだけで、検索処理自体には特別な末端処理を加えなくて良くなる。
** 木 [#j0b14123]
上記で色々解説されてる配列・スタック・キュー・リストなどは、どれも線形なデータ構造だ。一つの要素に接しているのは、直前の要素と直後の要素の二つだけなのが基本だ。~
一方で、木構造というのは枝分かれのあるデータ構造だ。一つの要素が複数の子要素を持っていて、図にするとちょうど広葉樹みたいな感じになるから木構造と言う。英語ではTreeだ。まんまだけど。~
ただし、大抵の場合、図示するときは木みたいに下から上に生えてくんじゃなくて、上から下にぶら下がるように書く。~
木構造で有名なのは、ファイルシステムだ。WindowsならCドライブがあって、その下にWindowsやProgram Filesやなんかがあって、Program Filesの下にはエロゲーのインストールされたフォルダがある。あれも一種の木構造だ。Linuxなら/ (ルートディレクトリ) があってetcとかusrとかhomeがあって、まあ構成は違うが後は同じだ。エロゲーはあんまりないと思うけど。~
後はXMLとかJSONとかも一種の木構造だし、ドメイン名の集合なんかも木構造に抽象化できる。~
ここからしばらく木構造に関して解説を加えよう。木構造の解説をするにあたって、基本的な用語を定義する。~
- ノード（節） 木構造を構成する基本単位。0個又は1個の親ノードと、0～複数個の子ノードを持つ。子ノードは必ず親ノードを持つ。~
- ルート（根） 木構造の一番根本にあるノード。任意の子ノードから親ノードを辿って行くと、必ずルートに辿り着く。ルートは親ノードを持たない。~
- リーフ（葉） ルートとは逆に、木構造の一番末端にあるノード。リーフは子ノードを持たない。~
- エッジ（辺） 親ノードと子ノードを結ぶ線。~
- 先祖ノード 任意の子ノードから辿って、ルートに辿り着くまでの経路にある全てのノード。~
- 子孫ノード 任意の親ノードから、子ノードを辿って到達することができる全てのノード。~
- 深さ 任意のノードのルートまでのノードの個数。ルートの深さは0~
- 高さ 任意のノードから一番深い子孫リーフまでのノードの個数。ルートの高さがその木構造の高さになる。~
- 深さ 任意のノードのルートまでのエッジの本数。ルートの深さは0~
- 高さ 任意のノードから一番深い子孫リーフまでのエッジの本数。ルートの高さがその木構造の高さになる。~
*** 二分木 [#d6d2cafb]
木構造のうち、子ノードの数が2個以下のものを2分木という。ノードを辿る際に右か左か終点かを求めれば良いだけなので、単純なアルゴリズムで実装できる。~
二分探索と相性が良く、実装が簡単なため良く利用される。~
以下で紹介するAVL木、赤黒木、ヒープは全て二分木の実装だ。~
*** AVL木 [#l4384105]
単純な二分木の構成だと、値を挿入する順番によっては単なるリスト構造と変わらない形になってしまう（挿入する値がソート済みの場合）~
そうなると、探索・挿入・削除の計算量がO(n)になってしまうため、平衡二分探索木という構造が考えられた。~
平衡二分探索木は、ノードの左右の深さがほぼ等しい二分木を言う。木構造のノード数がm (2^n≦m, m＜2^(n+1))の場合、平衡二分木の深さはおおよそn+1になる。おおよそ、というのは、アルゴリズムによってはそれなりに偏りが生まれる場合もあるからだ。~
平衡二分探索木は、ノードの左右の深さがほぼ等しい二分木を言う。木構造のノード数がm (2^n≦m, m＜2^(n+1))の場合、平衡二分木の高さはおおよそn+1になる。おおよそ、というのは、アルゴリズムによってはそれなりに偏りが生まれる場合もあるからだ。~
平衡二分探索木の探索のコストはO(log n)になる。~
AVLは平衡二分探索木のなかでも、厳密な平衡性を保つアルゴリズムだ。~
厳密な平衡性を保つためには、ツリーに偏りが生じた場合、回転と呼ばれる操作で平衡に直さなければならない。AVL木は挿入・削除の度に厳密な平衡性の判定と回転を行うため、挿入・削除にかかるコストが後述の赤黒木と比べて大きい。~
*** 赤黒木 [#x3cd9897]
赤黒木はあまり厳密に平衡性を保たない平衡二分探索木だ。具体的に言うと、最も深いリーフの深さが最も浅いリーフの深さの二倍になることがある。~
したがって、AVL木と比べると探索にかかるコストは大きい。~
一方で、赤黒木は挿入・削除時の回転の回数を減らすことができるため、AVL木と比べると挿入・削除のコストが小さい。~
赤黒木は動的なデータ構造、AVLは静的なデータ構造といった風に使い分けるといいかもしれない。~
*** ヒープ [#v35e1d11]
** グラフ [#f9136e1b]
*** 隣接行列表現 [#qbdd8249]
*** 隣接リスト表現 [#k4751445]
** ハッシュ表 [#f7c93b36]
*** 連鎖法 [#l66cfcc0]
*** オープンアドレス法 [#e44025a1]
*その他 [#bbfb5391]
**最大公約数(GCD: greatest common divisor) [#i9b377e0]
(ユークリッドの互除法)~
紀元前300年頃には既に存在した、最古のアルゴリズム。~
例 a0 = 497,a1 = 284とおく。
497 = 284 + a2 a2 = 213
284 = 213 + a3 a3 = 71
213 = 71 * 3 + a4 a4 = 0
つまり、497と284の最大公約数は71となる。
この計算手法をユークリッドの互除法と呼ぶ。
実装例:C言語
#include <stdio.h>
int gcd(int a0, int a1)
{
int a, b, tmp;
a = a0; b = a1;
while (b != 0) {
tmp = a % b; a = b; b = tmp;
}
return a;
}
上記GCD関数用のテストコード
int main(void)
{
int a0, a1, tmp;
printf("一番目の整数を入力してね >> ");
scanf("%d", &a0);
printf("二番目の整数を入力してね >> ");
scanf("%d", &a1);
if (a0 <= 0 || a1 <= 0) {
printf("0以下の数なんか入力すんなｗｗｗ : %d, %d\n", a0, a1);
exit(-1); // 異常終了
}
if (a0 < a1) { // 関数GCDではa0 > a1と仮定しているので値を入れ替える
tmp = a0; a0 = a1; a1 = tmp;
}
printf("%d と %d の最大公約数(GCD) = %d\n", a0, a1, gcd(a0, a1));
return 0;
}
** 参考リンク [#d212128a]
-[[C言語による最新アルゴリズム事典(Vevtor)>http://www.vector.co.jp/soft/data/prog/se002453.html]]~
『C言語による最新アルゴリズム事典』全ソースコード~
-[[アルゴリズム演習300題(Vector)>http://www.vector.co.jp/soft/data/prog/se078278.html]]~
「アルゴリズム演習３００題」（日刊工業新聞社刊）のＣ言語による解答例~
-[[アルゴリズム系書籍ソース目次ファイル(Vector)>http://www.vector.co.jp/soft/data/prog/se269457.html]]~
Vectorで公開されている~
『アルゴリズム演習300題』『C言語による最新アルゴリズム事典』用の目次ファイル~
-[[ソースコード探険隊 » アルゴリズムとデータ構造>http://www.codereading.com/algo_and_ds/]]~
データ構造の章では主に線形のデータ構造とグラフデータ構造を解説~
アルゴリズムの章では主に探索アルゴリズムと整列アルゴリズムを解説~
-[[Algorithm Collection>http://web.archive.org/web/20040208153438/http://alfin.mine.utsunomiya-u.ac.jp/~niy/algo/]]~
(web.archive)~
-[[Windowsプログラミング研究所 » ゲーム＆その他>http://www13.plala.or.jp/kymats/study/game_other.html]]~
実践(アルゴリズム中心)~
-[[京都大学OpenCourseWare » 工学部 » アルゴリズムとデータ構造入門 » 講義ノート>http://ocw.kyoto-u.ac.jp/ja/09-faculty-of-engineering-jp/bb30kg/lecturenote]]~
-[[九州大学大学院システム情報科学研究院 金子研究室 Web ページ » アルゴリズムとデータ構造>http://www.kkaneko.com/rinkou/algo/index.html]]~
//www.db.is.kyushu-u.ac.jp -> www.kkaneko.com 移転。
-[[Fussyのホームページ > アルゴリズムの紹介>http://fussy.web.fc2.com/algo/index.htm]]~
-[[アルゴリズム - osdev-j (MMA)>http://wiki.osdev.info/index.php?%A5%A2%A5%EB%A5%B4%A5%EA%A5%BA%A5%E0]]~
-[[アルゴリズム辞典 [無料]>http://dir.kotoba.jp/ddcat.cgi?k=algorism&w=2&mL=&DC=100&LC=100&fsz=2]]~
-[[ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40>http://zapanet.info/blog/item/1145]]~
-[[技術計算用Ｃプログラム ソース>http://www5.airnet.ne.jp/tomy/cpro/csource.htm]]~
アルゴリズムをCソースプログラムと共に紹介、ダウンロード・サービス
