この頁の解説貧弱すぎｗｗなめてんだろｗｗｗ
と思った奴は何か書いてくれ
英語ではリニアサーチ。
何のひねりもなく、先頭から末尾まで探していくだけのサーチです。
データが多くなると遅くなりがちですが、何の前提条件も無く使える手軽さが利点です。
シンプルなので、要素の数が１０個前後の小規模な配列に対してはかえって高速だったりします。
例:C言語(配列のアドレスとサイズを渡し、numと一致する要素のアドレスを返す)
int * LinearSearch(int * array , unsigned int size , int num) {
for (int i = 0 ; i < size ; i++) {
if(array[i] == num) return &array[i];
}
return NULL;
}
配列の要素数が増えれば増えただけ探索に時間がかかるようになります。
要素数10000の配列は、要素数10の配列の1000倍時間がかかるわけです。
このように、データ量と処理時間が単純に比例して増える事を「線形時間」とかO(n)とか表現したりします。
１番時間がかかるのは探しているデータが存在しない場合で、１番時間がかからないのは、先頭にあった場合です。
英語ではバイナリサーチ。
整列済みの要素群に対して実行します。 性質上、再帰を用いて実装される場合が多いです。
例: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 &array[center]; } //←発見！
end = center - 1;
}
else { //numは中間より後にある
begin = center + 1;
}
if(begin > end) return NULL; //探す範囲が無くなってしまった
}
}
整列の中央と探索対象を比較すると、その結果で整列の
左側あるいは右側だけに候補を絞ることができます。
そして、その搾られた候補に対して同じ要領で中央の値との比較と候補の絞り込みを繰り返していくと
いずれある時の中央の値あるいはただひとつに絞られた候補として
探索対象が現れます(整列に探索対象があれば)
要素数１の時の処理時間を基準にすると、要素数４でも３倍、８でも４倍、１６でも５倍……みたいな感じで増加が緩やかです。
１回の比較で、探索候補の半分を振るい落とせるためです。
このように、データ量が倍に増えても処理時間は緩やかにしか増えない事を「対数時間」とかO(log n)とか表現したりします。
線形探索のO(n)と比べるとデータ量の増加に強いものの、処理が少々複雑なため
要素が少ないうちは線形探索よりも遅かったりしますが、総合的にはこちらの方が断然速いと言えます。
世間にはあまり知られておらず、専門書にもまず載っていないが、
他のソートアルゴリズムに比べ極めて分かり易いアルゴリズムであり、
訓練をすれば猿はおろか犬でも習得できる。
初心者の坊や達を優しくソートの世界に導いてくれる方。
とても素直だけど、遅いので実戦の場に出ず教育者として活躍しています。
例: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;
}
}
}
}
隣り合ってる要素を比べて、並べたい順番になってなかったら入れ替える、という操作を繰り返すわけです。
要素が正しい位置に泡のように登っていくのでバブルソートと名付けられました。
単純ですが無駄な比較が多く、遅いです。
バブルソートの親戚。
挟みこむような動きで少しだけ無駄を減らす事に成功しました。
カクテルソート等とも呼ばれます。 オシャレですね。
バブルソートで走査中、最後に入れ替えがあった位置よりも後ろは、綺麗に並んでる事がわかります。
つまり、最後に入れ替えがあった位置を記録し、次からはそれ以降を無視すれば少し無駄が少なくなるわけです。
そこで更に、前方後方と交互に走査すれば、両方から範囲を狭める事が出来るので少しだけ効率が良くなるのです。
ぶっちゃけ大して変わらないとか言うな。
バブルソートの親戚。
色々な大きさの櫛を駆使します。
隣同士ではなく、まず適当に大きな間隔を開けて比較・交換をします。
どんどん間隔を小さくしていきつつ走査を繰り返し、最後は間隔が無くなり、隣同士を交換するようになります。
この隣同士の交換が終わった時、既にちゃんと整列出来てしまっています。
ずっと細かく見ていくよりも、最初は大雑把にやった方が効率が良いという事らしいです。
飛び飛びに揃えていくのが髪をとかす櫛（コム）のように見えるからこの名前がつきました。
手当たり次第に突っ込む単純な子ですが、状況次第ではなかなかの速さ。
大変に開放的な性格です。
例: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]); } //要素の交換
}
前から順に見ていき、要素を正しい位置に挿入していきます。
この「挿入」の操作そのものは、バブルソートと同じような要領です。離れた位置に挿入する程、比較や交換の回数が多くなります。
動きとしては、配列の前部に 整列したデータがどんどん溜まっていくような感じです。
ほとんど整列済みのデータなら離れた所まで挿入する事が少なくなるので、かなり高速になります。
挿入ソートの親戚。
やはり突っ込むばかりだけれど、少しずつ間隔を開けたりする賢さがあります。
別に貝殻が好きというわけではなく、Shellさんが開発しただけだったりする。
挿入ソートとシェルソートの関係は、バブルソートとコムソートのようなもので
「最初は大雑把にやって、最後だけ細かく仕上げた方が効率が良い」という事を利用しています。
具体的には、ある程度の間隔を開けて挿入ソートを行い、どんどん間隔を狭くしていくのです。
馬鹿ソートとか言われたりするけど気にしない明るい子。
とりあえず一番小さいのを探し続ければそのうち揃うよね！
配列を走査し、最も小さい(ソート後に端に来る)データを見つけてから、それを１番最初のデータと交換します。
そして、２番目の小さいデータ、３番目に小さいデータ、と次々に処理していきます。
最後の１個を見るまで「一番小さい」かどうかはわからないため、結局全部見ていく事になり、大して効率は良くありません。
交換回数は少ないため、バブルソートよりは高速と言えます。
最速の名をほしいままにしているが、たまにさぼっちゃう気まぐれ屋さん
スレンダーな子です
いつも手を抜くことなく、速さを常に追求する努力家
クイックソートには負け越しているのをくやしがっている
他の子より大きいのが悩み
まず、配列を真っ二つに分けます。 分かれて出来た２つの配列を、更にそれぞれ真っ二つにします。
これを繰り返し、完全にバラバラになってしまうまで分割してしまいます。
分割が終わったら、今度は逆にマージ(合併)していきます。 この時、上手く順番に並ぶようにマージします。
マージして出来た配列を更にマージしていって、最後にたった１つの配列になった時、ソートが完了しています。
綺麗に並んだ配列２つをマージする時は、それぞれの配列の「端だけ」比較すればいいので比較回数が少なくて済むのがポイント。
（１，４，５）と（２，３，６）なら、まず左端の１と２だけを、次は４と２だけを……という風に。
マージに余分なメモリ領域が必要な事と、平均するとクイックソートより僅かに遅いのが難ですが、かなり速いソートの１つです。
それだけじゃクイックソート使えばいいじゃないかとなりますが、こちらは速度が安定しています。
また、安定ソートでもあります。 なんとなく堅牢なイメージがありますね。
他にもビンソートとか色々あだ名がある。
趣味で大量にバケツを集めすぎて家を崩壊させてしまうような性格のせいで
秘めたポテンシャルを発揮出来ずにいる。
「０～１００点のテストの点数をソートするんなら、１０１個のバケツを並べてぶちこんで順に取りだしゃいいじゃん！」
という事をマジでやるというトンでもなく豪快なソートです。
比較と入れ替えを繰り返すものが多いソートの中で、非常に独特な性質を持っています。
まず、データがいくら増えようと「バケツに入れる」という操作の回数が単に増えていくだけなので、なかなか重くなりません。
（データ量が千倍になればクイックソートでも大体１万倍重くなりますが、バケットソートは、単に千倍です）
非常に速いソートですが、当然弱点があり「バケツを用意するために大量のメモリが必要」なのです。
例に出した0～100の範囲ならまだいいのですが、32bitのint型で表現出来る全ての数をソートしようとしたなら
範囲は-2,147,483,648～2,147,483,647という事で、4294967296個のバケツが必要になります。
また、ソートしたいデータに同じ数値が重複してる場合があります(テストで同じ70点を取った子が何人もいたとか)から
バケツは単純な配列として用意する事は出来ません。配列には１つのデータしか入れられないのです。
大抵はリンクリストの配列みたいな実装になるのですが、リンクリストにも余分なメモリが必要なので更に酷くなります。
このように、使うための条件は厳しいものの、クイックソートよりも高速に処理出来たりなどロマンが溢れるソートです。
バケットソートの親戚。
一応バケットソートよりはマシなものの、やはり家が崩壊しがち。
バケットソートはリンクリストを使った実装だと 動的なメモリの確保や条件分岐が頻繁に起こり、折角の速度が出せません。
なので、もっと上手い方法は無いのか、という事で考え出されたものがこれです。
まず、以下のようなデータがあったとします。
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番目から始まっている事がわかります。
これを利用し「何番目から始まるか」という数だけをバケツに入れれば、リストでなく単なる配列で実装でき
同じ数値が重複してても、その要素を処理するたびに「何番目から始まるか」のバケツを＋１していくだけで対処出来ます。
このような実装をすれば リンクリストのための余分なメモリも、その確保にかかる時間も、分岐も、少なく済むため高速なのです。
ただし、要素の数を数えるための走査と 実際にソートをするための走査で、合計２回の走査が必要になるため
ソートしようとしているデータの規模によってはかえって低速かもしれません。
(リンクリスト用のメモリの動的確保や分岐は結構重いので、測ってみると大抵はこちらの方式の方が速かったりしますが)
バケットソートの友人。 英語にするとラディックスソート。
極限られた状況でのみ他を圧倒する速さを出す可能性を秘めている
しかし、あまり活躍の機会がないのでたまに忘れ去られてたりする。
基数というのは数を表す際に基本となるまとまりの事で、例えば「○進数」の○の部分です。
１桁目、２桁目、３桁目のように桁ごとにソートしても、順番さえ保存されてれば上手い事揃う、という事を利用するソートです。
以下のようなデータがあったとします。
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的にキリの良い２のべき乗で区切ってシフトやマスクを駆使すればなお良し。
「桁ごとに区切っても揃う」という原理は別にバケットソートでなくても通用するのですが
その他のソートだと単に処理の回数を増やすだけで何の利点も無いので、大抵バケットソートの改良版として紹介されます。
「バケットソートは超速いけど、メモリ喰いすぎるのがちょっと……」という方にお勧め。
範囲さえある程度絞れるならクイックソートよりも普通に高速に実装出来ます。
工夫次第で負の数を含んでたり浮動小数を扱ったりする場合にも対応出来ます。
バケットソートの親戚。
一見、数学的で難解な事を考えていそうな雰囲気ですが、割と豪快な性格です。
写像とは小難しそうな数学用語ですが、「２つの数字の集まりを対応させる」というだけの単純な概念です。
添字を入れると要素が出てくる配列も 添字→要素の写像と言えます。
「逆写像」というと、その逆になり、要素→添字という写像になるわけですが
そういう配列＝バケツと考えると、実の所それはただのバケットソートという事になります。
バケットソートとの違いは「値が同じ要素があった時の対処」の部分だけで、事実上それだけが逆写像ソートのアイデンティティです。
その対処の仕方とは「添字をポインタ代わりに使ってリンクリストのようなものを作る」というもので
リンクリストでいう next に対応する添字の値を確保するため、ソートする配列と同じサイズのnextの配列を用意するのです。
この配列のおかげで、バケツに１つの要素しか入れる必要が無くなっているのがポイント。
ぶっちゃけバケットソートや分布数えソートを使えば済むので、知ってる人すら少ないマニアックなソートです。
バブルソートの親戚。
チームプレーや流れ作業が得意な方。
バブルソートは隣合った要素を比較、交換していくので
「１ ２」「２ ３」「３ ４」を添字として処理していくわけですが
奇遇転置ソートは「１ ２」「３ ４」「５ ６」のような「奇数 偶数」要素を処理と
「２ ３」「４ ５」「６ ７」のような「偶数 奇数」要素の処理を交互に行う、というような動きをします。
処理の回数そのものはバブルソートと大して変わらないのですが
ポイントは「１ ２」「２ ３」 だと「２」が かぶってますが「１ ２」「３ ４」だと何もカブらない、という点です。
つまり１回１回の処理が独立しているため、複数のCPUを使って並列に処理しやすいのです。
いくら大量にCPUがあっても、走っているスレッドが１つだけなら１個分の性能しか出せません。
CPUを増やせば増やしただけ速く出来るという限界の高さに並列処理の価値があるわけです。
逆に言えば、並列処理が出来る環境でなければ大して役に立たないソートです。
共有のソート。
部下をを団結させ、隊列を整えるチームワークを発揮させるやり手の指揮官です。
一次元の住人が多いソート業界では珍しい二次元の世界の住人です。
まずは、要素数[30]の配列→[6][5]の二次元配列、みたいな感じに分割します。
そして１行目[1][i] ２行目[2][i] ３行目[3][i]……のように各行別々にソートするのと
１列目[i][1] ２列目[i][2]……のように各列別々にソートするのを交互に行っていきます。
各行や列は、それぞれ独立しているので、並列に処理が出来ます。
「奇数行は左が小さくなるように、偶数行は、右が小さくなるようにソート」
「列は、上が小さくなるようにソート」
これを交互に繰り返す事で、小さい値は左右にクネクネ動きながら上に登っていきます。かなりトリッキー。
ちなみに、各行に対して行うソートは何を使ってもいいですが
奇遇転置ソートやマージソート等を使うと並列性を更に上げられるでしょう。
複数のCPUを搭載している状態なら、かなりの速度向上が期待出来ます。
もちろん、並列処理が出来る環境でなければ、さほどのスピードは出ません。
究極のスピードを誇っているものの、力を出しすぎると地球が吹き飛ぶため本気を出せない。
が・・・あ・・・離れろ・・・死にたくなかったら早く俺から離れろ！！
理論上最高の速度が出るソートですが、やってる事は凄く単純で
if や else等の分岐を大量に使って最小限の回数の比較、交換しかしない、というだけのものだったりします。
性質上、ソートする配列のサイズがわかってて、しかも極端に要素が少ないものにしか使えません。
要素の数が４つだけの場合でも使うifやelseの数は数十個に及び、６つを超えたあたりで百を超えます。
書くのが異様に面倒なので、実際に使いたいなら そういうコードを生成するジェネレータを作りましょう。
また、当然実行ファイルのサイズも爆発的に増えていきます。
何億回もソートを繰り返すような処理が必要でなければコストに見合ったリターンは得られないソートです。
※どうやら上記のソートは本来の(？)バイ・トニックソートとは違うもののようです。
本格的なバイ・トニックソートは、むしろマージソートに近く、並列処理なんかに使われるものなんだとか。
正確な情報はちょっと持ってないので、知ってる人は編集してくだしあ＞＜
等価なデータの順番がソート前と同じという事が保証されているソートの事を「安定ソート」と呼びます。
言葉にすると難しいですので例を出しましょう。
例えば、このようなデータがあるとします。
データ 「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の方が左にあった」という事で、必ず結果１になります。
クイックソート等の安定でないソートを用いると、結果１になるか結果２になるかは全くわかりません。
「そんなのどうでもいいから速いほうがいいよ」という場合にクイックソートを使い、順番が重要な時は安定なソートを使うわけです。
多くのソートが安定ですが
コムソート シェルソートなどの間隔を開けて処理をするソートや
クイックソート等は、安定でないソートとして知られています。
安定と言われているソートでも、実装の仕方によっては安定でなくす事も出来てしまいますが
あえて安定にしない事で得するような事はあまり無いです。
また、基数ソートのように安定なバケットソートを利用しないと実現出来ないものもあります。
「干し草の山」の意。
名前の通り、新しいデータを上に積み上げていき、下に埋もれた古いデータを取り出すためには
上のデータを先に取り出さなければならない後入先出(あといれさきだし)の構造です。
「古いデータは取っておき、新しいデータに対して色々な処理をしてから利用する」ような場面で使われます。
例えば関数・メソッドの呼び出しの際に使われるコールスタックなんかが有名。
ローカル変数は他の関数を呼び出してから戻ってくるまでずっと保存されてますが、それはスタック上にあるからなのです。
ところてんだよところてん
「待ち行列」の意。
名前の通り、古いデータは新しいデータの後ろに並び、新しいデータが出て行くまで取り出せません。
先入先出(さきいれさきだし)の構造です。
「先のデータの処理が終わるまで、後から来たデータにちょっと待ってもらう」ような場面で使われます。
サーバーなんかは、すぐに処理出来ない大量のリクエストが来た場合のためのキューを持っているのが普通です。
(優先度が高いリクエストはキューで待たせず割り込ませてあげるような機能もありがちです)
Deque。 スタックとキューを合わせたような機能を持っています。
具体的には「前から入れる」「前から出す」「後から入れる」「後から出す」の全てが出来ます。
長所：両端へのデータ挿入がO(1) 添字アクセス可能
短所：要素の中央の挿入、削除が遅い
削除、挿入は平均すると動的配列より優れるが、単純なアクセスではやや劣る。
連結リストとも呼ばれる非常に一般的なデータ構造の一種。
ある箱を仮想的に考え、それと別のはことをつなぐようなイメージのデータ構造。
箱は変数を表すと考えれば、箱同士のつなぎ方によっていくつかの種類に分かれる。
多くの言語では、箱と連結部分を一括して扱うために、構造体などを用いる。
最近のモダンな言語ではライブラリにリスト構造があらかじめ用意されている場合が多い。
また、Lispなど「リスト構造ありき」で言語設計がなされているプログラム言語も少数ながら存在する。
似たようなデータ構造に配列が存在するが、N番目の要素にアクセスする時に必要な計算時間が、配列ではO(1)なのに対して、リストではO(N)かかるという点が大きく異なる。
従って、使用できるメモリーの割合や扱うデータの特性によっては、リストよりも配列を利用したほうが有効な場合もある。