* アルゴリズムとデータ構造 [#p8c4a8bb] この頁何もねぇwwなめてんだろwww~ と思った奴は何か書いてくれ #contents * アルゴリズム [#v958b98c] ** 探索 [#i297b629] *** 線形探索 [#oc5e463b] *** 二分探索 [#qce356fb] *** ハッシュ表探索 [#i2c23e92] ** 整列 [#h84db045] *** ボゴソート [#h92fd60b] 世間にはあまり知られておらず、専門書にもまず載っていないが、~ 他のソートアルゴリズムに比べ極めて分かり易いアルゴリズムであり、~ 訓練をすれば猿はおろか犬でも習得できる。 ***バブルソート [#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; } } } } 隣り合ってる要素を比べて、並べたい順番になってなかったら入れ替える、という操作を繰り返すわけです。~ 要素が正しい位置に泡のように登っていくのでバブルソートと名付けられました。~ 単純ですが無駄な比較が多く、遅いです。 ***シェーカーソート [#eaad47d0] バブルソートの親戚。~ 挟みこむような動きで少しだけ無駄を減らす事に成功しました。~ ~ バブルソートで走査中、最後に入れ替えがあった位置よりも後ろは、綺麗に並んでる事がわかります。~ つまり、最後に入れ替えがあった位置を記録し、次からはそれ以降を無視すれば少し無駄が少なくなるわけです。~ そこで更に、前方後方と交互に走査すれば、両方から範囲を狭める事が出来るので少しだけ効率が良くなるのです。 ***コムソート [#d6da5661] バブルソートの親戚。~ 色々な大きさの櫛を駆使します。~ ~ 隣同士ではなく、まず適当に大きな間隔を開けて比較・交換をします。~ どんどん間隔を小さくしていきつつ走査を繰り返し、最後は間隔が無くなり、隣同士を交換するようになります。~ この隣同士の交換が終わった時、既にちゃんと整列出来てしまっています。~ ずっと細かく見ていくよりも、最初は大雑把にやった方が効率が良いという事らしいです。~ 飛び飛びに揃えていくのが髪をとかす櫛(コム)のように見えるからこの名前がつきました。~ ***挿入ソート [#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]); } //要素の交換 } 前から順に見ていき、要素を正しい位置に挿入していきます。~ この「挿入」の操作そのものは、バブルソートと同じような要領です。離れた位置に挿入する程、比較や交換の回数が多くなります。~ 動きとしては、配列の前部に 整列したデータがどんどん溜まっていくような感じです。~ ほとんど整列済みのデータなら離れた所まで挿入する事が少なくなるので、かなり高速になります。 *** シェルソート [#ua3da88b] 挿入ソートの親戚。~ やはり突っ込むばかりだけれど、少しずつ間隔を開けたりする賢さがあります。~ 別に貝殻が好きというわけではなく、Shellさんが開発しただけだったりする。~ ~ 挿入ソートとシェルソートの関係は、バブルソートとコムソートのようなもので~ 「最初は大雑把にやって、最後だけ細かく仕上げた方が効率が良い」という事を利用しています。~ 具体的には、ある程度の間隔を開けて挿入ソートを行い、どんどん間隔を狭くしていくのです。 *** クイックソート [#h788cb12] 最速の名をほしいままにしているが、たまにさぼっちゃう気まぐれ屋さん~ スレンダーな子です~ *** マージソート [#y34cbfeb] いつも手を抜くことなく、速さを常に追求する努力家~ クイックソートには負け越しているのをくやしがっている~ 他の子より大きいのが悩み~ ~ まず、配列を真っ二つに分けます。 分かれて出来た2つの配列を、更にそれぞれ真っ二つにします。~ これを繰り返し、完全にバラバラになってしまうまで分割してしまいます。~ 分割が終わったら、今度は逆にマージ(合併)していきます。 この時、上手く順番に並ぶようにマージします。~ マージして出来た配列を更にマージしていって、最後にたった1つの配列になった時、ソートが完了しています。~ 綺麗に並んだ配列2つをマージする時は、それぞれの配列の「端だけ」比較すればいいので比較回数が少なくて済むのがポイント。~ (1,4,5)と(2,3,6)なら、まず左端の1と2だけを、次は4と2だけを……という風に。~ マージに余分なメモリ領域が必要な事と、平均するとクイックソートより僅かに遅いのが難ですが、かなり速いソートの1つです。 *** バケットソート [#b490822c] 他にもビンソートとか色々あだ名がある。~ 趣味で大量にバケツを集めすぎて家を崩壊させてしまうような性格のせいで~ 秘めたポテンシャルを発揮出来ずにいる。 *** 分布数えソート [#r779f37a] バケットソートの親戚。~ 一応バケットソートよりはマシなものの、やはり家が崩壊しがち。~ *** 基数ソート [#od200194] バケットソートの親戚。 英語にするとラディックスソート。 極限られた状況でのみ他を圧倒する速さを出す可能性を秘めている~ しかし、あまり活躍の機会がないのでたまに忘れ去られてたりする。 *** バイトニックソート [#ud51908c] 究極のスピードを誇っているものの、力を出しすぎると地球が吹き飛ぶため本気を出せない。~ が・・・あ・・・離れろ・・・死にたくなかったら早く俺から離れろ!!~ ~ 理論上最高の速度が出るソートですが、やってる事は凄く単純で~ if や else等の分岐を大量に使って最小限の回数の比較、交換しかしない、というだけのものだったりします。~ 性質上、ソートする配列のサイズがわかってて、しかも極端に要素が少ないものにしか使えません。~ 要素の数が4つだけの場合でも、使うifやelseの数は数十個に及び、6つを超えたあたりで百を超えます。~ 書くのが異様に面倒なので、実際に使いたいなら、そういうコードを生成するジェネレータを作りましょう。~ また、当然実行ファイルのサイズも爆発的に増えていきます。 ~ 何億回もソートを繰り返すような処理が必要でなければコストに見合ったリターンは得られないソートです。 ** データ構造 [#wc0c038f] ** 参考リンク [#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]]~ 「アルゴリズム演習300題」(日刊工業新聞社刊)のC言語による解答例~ -[[アルゴリズム系書籍ソース目次ファイル(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/jp/engineering/course07/lecturenote.htm]]~ -[[九州大学 大学院システム情報科学研究院 金子研究室 Web ページ » アルゴリズムとデータ構造>http://www.db.is.kyushu-u.ac.jp/rinkou/algo/index.html]]~ -[[Fussyのホームページ > アルゴリズムの紹介>http://www2.starcat.ne.jp/~fussy/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]]~ -[[技術計算用Cプログラム ソース>http://www5.airnet.ne.jp/tomy/cpro/csource.htm]]~ アルゴリズムをCソースプログラムと共に紹介、ダウンロード・サービス