この頁の解説貧弱すぎｗｗなめてんだろｗｗｗ
と思った奴は何か書いてくれ
英語ではリニアサーチ。
何のひねりもなく、先頭から末尾まで探していくだけのサーチです。
データが多くなると遅くなりがちですが、何の前提条件も無く使える手軽さが利点です。
シンプルなので、要素の数が１０個前後の小規模な配列に対してはかえって高速だったりします。
例: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さんが開発しただけだったりする。
挿入ソートとシェルソートの関係は、バブルソートとコムソートのようなもので
「最初は大雑把にやって、最後だけ細かく仕上げた方が効率が良い」という事を利用しています。
具体的には、ある程度の間隔を開けて挿入ソートを行い、どんどん間隔を狭くしていくのです。
馬鹿ソートとか言われたりするけど気にしない明るい子。
とりあえず一番小さいのを探し続ければそのうち揃うよね！
配列を走査し、最も小さい(ソート後に端に来る)データを見つけてから、それを１番最初のデータと交換します。
そして、２番目の小さいデータ、３番目に小さいデータ、と次々に処理していきます。
最後の１個を見るまで「一番小さい」かどうかはわからないため、結局全部見ていく事になり、大して効率は良くありません。
交換回数は少ないため、バブルソートよりは高速と言えます。
最速の名をほしいままにしているが、たまにさぼっちゃう気まぐれ屋さん
スレンダーな子です
いつも手を抜くことなく、速さを常に追求する努力家
クイックソートには負け越しているのをくやしがっている
他の子より大きいのが悩み
まず、配列を真っ二つに分けます。 分かれて出来た２つの配列を、更にそれぞれ真っ二つにします。
これを繰り返し、完全にバラバラになってしまうまで分割してしまいます。
分割が終わったら、今度は逆にマージ(合併)していきます。 この時、上手く順番に並ぶようにマージします。
マージして出来た配列を更にマージしていって、最後にたった１つの配列になった時、ソートが完了しています。
綺麗に並んだ配列２つをマージする時は、それぞれの配列の「端だけ」比較すればいいので比較回数が少なくて済むのがポイント。
（１，４，５）と（２，３，６）なら、まず左端の１と２だけを、次は４と２だけを……という風に。
マージに余分なメモリ領域が必要な事と、平均するとクイックソートより僅かに遅いのが難ですが、かなり速いソートの１つです。
それだけじゃクイックソート使えばいいじゃないかとなりますが、こちらは速度が安定しています。
また、安定ソートでもあります。 なんとなく堅牢なイメージがありますね。
他にもビンソートとか色々あだ名がある。
趣味で大量にバケツを集めすぎて家を崩壊させてしまうような性格のせいで
秘めたポテンシャルを発揮出来ずにいる。
バケットソートの親戚。
一応バケットソートよりはマシなものの、やはり家が崩壊しがち。
バケットソートの友人。 英語にするとラディックスソート。
極限られた状況でのみ他を圧倒する速さを出す可能性を秘めている
しかし、あまり活躍の機会がないのでたまに忘れ去られてたりする。
バケットソートの親戚。
一見、数学的で難解な事を考えていそうな雰囲気ですが、割と豪快な性格です。
写像とは小難しそうな数学用語ですが、「２つの数字の集まりを対応させる」というだけの単純な概念です。
添字を入れると要素が出てくる配列も 添字→要素の写像と言えます。
「逆写像」というと、その逆になり、要素→添字という写像になるわけですが
そういう配列＝バケツと考えると、実の所それはただのバケットソートという事になります。
バケットソートとの違いは「値が同じ要素があった時の対処」の部分だけで、事実上それだけが逆写像ソートのアイデンティティです。
その対処の仕方とは「添字をポインタ代わりに使ってリンクリストのようなものを作る」というもので
リンクリストでいう next に対応する添字の値を確保するため、ソートする配列と同じサイズのnextの配列を用意するのです。
この配列のおかげで、バケツに１つの要素しか入れる必要が無くなっているのがポイント。
ぶっちゃけバケットソートや分布数えソートを使えば済むので、知ってる人すら少ないマニアックなソートです。
バブルソートの親戚。
チームプレーや流れ作業が得意な方。
バブルソートは隣合った要素を比較、交換していくので
「１ ２」「２ ３」「３ ４」と処理していくわけですが
奇遇転置ソートは「１ ２」「３ ４」「５ ６」のような「奇数 偶数」要素を処理と
「２ ３」「４ ５」「６ ７」のような「偶数 奇数」要素の処理を交互に行う、というような動きをします。
処理の回数そのものはバブルソートと大して変わらないのですが
ポイントは「１ ２」「２ ３」 だと「２」が かぶってますが「１ ２」「３ ４」だと何もカブらない、という点です。
つまり１回１回の処理が独立しているため、複数のCPUを使って並列に処理しやすいのです。
いくら大量にCPUがあっても、走っているスレッドが１つだけなら１個分の性能しか出せません。
CPUを増やせば増やしただけ速く出来るという限界の高さに並列処理の価値があるわけです。
逆に言えば、並列処理が出来る環境でなければ大して役に立たないソートです。
共有のソート。
部下をを団結させ、隊列を整えるチームワークを発揮させるやり手の指揮官です。
一次元の住人が多いソート業界では珍しい二次元の世界の住人です。
まずは、要素数[30]の配列→[6][5]の二次元配列、みたいな感じに分割します。
行や列は、それぞれ独立しているので、並列に処理が出来ます。
「奇数行は左が小さくなるように、偶数行は、右が小さくなるようにソート」
「列は、上が小さくなるようにソート」
これを交互に繰り返す事で、小さい値は左右にクネクネ動きながら上に登っていきます。かなりトリッキー。
ちなみに、各行に対して行うソートは何を使ってもいいですが
奇遇転置ソートやマージソート等を使うと並列性を更に上げられるでしょう。
複数の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の方が左にあった」という事で、必ず結果１になります。
クイックソート等の安定でないソートを用いると、結果１になるか結果２になるかは全くわかりません。
「そんなのどうでもいいから速いほうがいいよ」という場合にクイックソートを使い、順番が重要な時は安定なソートを使うわけです。
多くのソートが安定ですが
コムソート シェルソートなどの間隔を開けて処理をするソートや
クイックソート等は、安定でないソートとして知られています。
安定と言われているソートでも、実装の仕方によっては安定でなくす事も出来てしまいますが
あえて安定にしない事で得するような事はあまり無いです。
また、基数ソートのように安定なバケットソートを利用しないと実現出来ないものもあります。
連結リストとも呼ばれる非常に一般的なデータ構造の一種。
ある箱を仮想的に考え、それと別のはことをつなぐようなイメージのデータ構造。
箱は変数を表すと考えれば、箱同士のつなぎ方によっていくつかの種類に分かれる。
多くの言語では、箱と連結部分を一括して扱うために、構造体などを用いる。
最近のモダンな言語ではライブラリにリスト構造があらかじめ用意されている場合が多い。
また、Lispなど「リスト構造ありき」で言語設計がなされているプログラム言語も少数ながら存在する。
似たようなデータ構造に配列が存在するが、N番目の要素にアクセスする時に必要な計算時間が、配列ではO(1)なのに対して、リストではO(N)かかるという点が大きく異なる。
従って、使用できるメモリーの割合や扱うデータの特性によっては、リストよりも配列を利用したほうが有効な場合もある。