この頁の解説貧弱すぎｗｗなめてんだろｗｗｗ
と思った奴は何か書いてくれ
英語ではリニアサーチ。
何のひねりもなく、先頭から末尾まで探していくだけのサーチです。
データが多くなると遅くなりがちですが、何の前提条件も無く使える手軽さが利点です。
シンプルなので、要素の数が１０個前後の小規模な配列に対してはかえって高速だったりします。
例: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さんが開発しただけだったりする。
挿入ソートとシェルソートの関係は、バブルソートとコムソートのようなもので
「最初は大雑把にやって、最後だけ細かく仕上げた方が効率が良い」という事を利用しています。
具体的には、ある程度の間隔を開けて挿入ソートを行い、どんどん間隔を狭くしていくのです。
最速の名をほしいままにしているが、たまにさぼっちゃう気まぐれ屋さん
スレンダーな子です
いつも手を抜くことなく、速さを常に追求する努力家
クイックソートには負け越しているのをくやしがっている
他の子より大きいのが悩み
まず、配列を真っ二つに分けます。 分かれて出来た２つの配列を、更にそれぞれ真っ二つにします。
これを繰り返し、完全にバラバラになってしまうまで分割してしまいます。
分割が終わったら、今度は逆にマージ(合併)していきます。 この時、上手く順番に並ぶようにマージします。
マージして出来た配列を更にマージしていって、最後にたった１つの配列になった時、ソートが完了しています。
綺麗に並んだ配列２つをマージする時は、それぞれの配列の「端だけ」比較すればいいので比較回数が少なくて済むのがポイント。
（１，４，５）と（２，３，６）なら、まず左端の１と２だけを、次は４と２だけを……という風に。
マージに余分なメモリ領域が必要な事と、平均するとクイックソートより僅かに遅いのが難ですが、かなり速いソートの１つです。
それだけじゃクイックソート使えばいいじゃないかとなりますが、こちらは速度が安定しています。
また、安定ソートでもあります。 なんとなく堅牢なイメージがありますね。
他にもビンソートとか色々あだ名がある。
趣味で大量にバケツを集めすぎて家を崩壊させてしまうような性格のせいで
秘めたポテンシャルを発揮出来ずにいる。
バケットソートの親戚。
一応バケットソートよりはマシなものの、やはり家が崩壊しがち。
バケットソートの親戚。 英語にするとラディックスソート。
極限られた状況でのみ他を圧倒する速さを出す可能性を秘めている
しかし、あまり活躍の機会がないのでたまに忘れ去られてたりする。
究極のスピードを誇っているものの、力を出しすぎると地球が吹き飛ぶため本気を出せない。
が・・・あ・・・離れろ・・・死にたくなかったら早く俺から離れろ！！
理論上最高の速度が出るソートですが、やってる事は凄く単純で
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の方が左にあった」という事で、必ず結果１になります。
クイックソート等の安定でないソートを用いると、結果１になるか結果２になるかは全くわかりません。
「そんなのどうでもいいから速いほうがいいよ」という場合にクイックソートを使い、順番が重要な時は安定なソートを使うわけです。
多くのソートが安定ですが
コムソート シェルソートなどの間隔を開けて処理をするソートや
クイックソート等は、安定でないソートとして知られています。
また、実装の仕方によって安定になったりそうでなくなったりするソートや
基数ソートのように安定なバケットソートを利用しないと実現出来ないものもあります。