この頁何もねぇｗｗなめてんだろｗｗｗ
と思った奴は何か書いてくれ
世間にはあまり知られておらず、専門書にもまず載っていないが、
他のソートアルゴリズムに比べ極めて分かり易いアルゴリズムであり、
訓練をすれば猿はおろか犬でも習得できる。
初心者の坊や達を優しくソートの世界に導いてくれる方。
とても素直だけど、遅いので実戦の場に出ず教育者として活躍しています。
例: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の数は数十個に及び、６つを超えたあたりで百を超えます。
書くのが異様に面倒なので、実際に使いたいなら、そういうコードを生成するジェネレータを作りましょう。
また、当然実行ファイルのサイズも爆発的に増えていきます。
何億回もソートを繰り返すような処理が必要でなければコストに見合ったリターンは得られないソートです。