ソートの概略
隣接要素の並べ替えを先頭から順に行い、列の末尾まで比較が終われば先頭に戻り、並べ替えを繰り返す。
末尾要素からソートが完了していく。
特徴は、大きい値が。水の中を浮き上がっていく気泡のごとく列の末尾に移動していくこと。
バブルソートの派生。コムとは「櫛」のこと。
最初は交換幅を大きく取って"櫛けずり"、次第に小さくしていく。
交換幅の縮小比率は1.3(計算後の小数点以下は切り捨て)で、これは考案者の大量試行による分析によって平均的最速になるように得られた"経験則"である。。
コムソートの派生。
交換幅が9、10の時は11に切り上げることで、櫛けずりの効率を上げたものと言われている。
隣接要素の並べ替えを「先頭から順に」「末尾から順に」を交互に行う。
先頭、末尾要素がそれぞれ順番にソートが完了していく。
特徴は、比較対称が先頭と末尾を行ったり来たりすることで、カクテルのシェーカーのように左右に振られていく様。
ソート済みの部分列の末尾に1要素追加して、隣接並べ替えで追加要素を適切な位置に持っていく。
見た目は素朴な挿入ソートと同じになる。
選択ソートの派生。「ヒープ」とは「固まり」や「積み重ね」の意味を持つが、計算機科学では「子ノードより親ノードのほうが大きい木構造」を指す。
最初に与えられた数列上に二分ヒープ木を作成し、末尾の要素をヒープ木から取り出していくことでソートをする。
ソート済みの列にこのソートを使うと、すごく無駄。
ヒープソートに使うヒープ木に、二項ヒープ木を用いてみた邪道ソート。
ソート列によって性能に大きなムラが出る。
使えそうな用途は思いつかないが、二項ヒープ木は木同士のマージ
ピボット(軸)に対して大か小かで列を分割するソート。
ピボットは、部分列の先頭を用いたり、乱数で選択するなどがある。
概ね高速にソートが完了するが、偶然もしくは意図的に相性の悪い初期列に当たると「ピボットとの大小比較回数」が多くなり、
ソート時間が長いという既知の問題も抱えている。
※このデモでは、「大小比較」のみの場合はフレームに加えていないため、最悪パターンを引いても高速に完了するように見える。
「モノトニック」は単調減少や単調増加の「単調」を示す数学用語。
「バイトニック」を日本語に訳すとすれば「二階調」、簡単に言えば「山型、谷型の関数」。
バイトニック数列を同じ添字(変数)に対し「小の値」「大の値」となる二つの小数列に分割し、それを繰り返して、ソートをする。
バイトニック数列、およびそれを上記操作で分割してできる小数列には、
上記操作で(互いの添字に関わらず)「小さい値の数列」と「大きい値の数列」に分けることができる。
ソート列は有限な為、分割を繰り返すことで必ず小数列の要素が1に到達し、上記の大小関係の性質によりソートが完了する。
隣り合うブロックのソートを「降順」「昇順」互い違いにすることでより大きいバイトニック数列にマージし、ソートを再帰させる。
素朴な実装だとソート列の要素数が2の冪乗でないと適用できないアルゴリズムな為
ダミー要素(例えばどの要素よりも大きい要素)を入れて2の冪乗個に水増しする等の工夫が必要になる。
特徴は、細かい「山」を大きな「山」に順次結合させていくこと。
バイトニックソートを逐次処理に切り替えてシミュレート。
ソート対象をブロック単位で視覚化しています。
基本的なバイトニックソートは、バイトニック数列を作る都合上逆順の比較交換を伴う。
正順の比較交換のみで行うために、マージ過程の1段階目の比較交換の組を調整したソート。
このようにすることで、マージ過程では正順のソート列同士の結合になる。
また、範囲外の要素との比較を無視することで、任意の数列に対して仮想的に2の冪乗要素数の初期配列とみなして適用できる。
隣同士の要素の比較を「奇数要素とその次の要素」「偶数要素とその次の要素」で繰り返し、並列化に対応した「バブルソート」の応用形。安定ソート。
特徴は、左右に数値が動いていく様子。
奇遇転置ソートを逐次処理に切り替えてシミュレート。
比較対象をビットの排他的論理和で求めていく。
例えば交換対象を計算するためのビットを「5=00000101(二進数)」とすれば、
0番目の数は5番目と比較し、9番目(=00001001)の数は5との排他的論理和を取って12番目(=00001100)の数と比較をする。
比較して、小さい番号に小さい数を、大きい番号に大きい数となるようにソートする。
交換対象を計算するためのビットは、0から2のn乗までを数を順に変えていく。（要素数＜2のn乗）
こうすることで、「マージソート」のような小ソート列を結合していくような様相を得る。
並列計算が可能なソートではあるが、奇遇転置ソートと同等のソート回数が必要になる。
交換対象を計算するためのビットは、上手く調整することにより、バイトニックソートと同等のソート回数まで抑えることが出来る。
比較対象をビットの排他的論理和で求めていく。
例えば交換対象を計算するためのビットを「5=00000101(二進数)」とすれば、
0番目の数は5番目と比較し、9番目(=00001001)の数は5との排他的論理和を取って12番目(=00001100)の数と比較をする。
比較して、小さい番号に小さい数を、大きい番号に大きい数となるようにソートする。
交換対象を計算するためのビットは、2のn乗から0までを数を順に変えていく。（要素数＜2のn乗）
こうすることで、「クイックソート」のような数値を大小で分割するような様相を得る。
並列計算が可能なソートではあるが、奇遇転置ソートと同等のソート回数が必要になる。
奇遇転置ソートをカスタマイズ。(K.Mikuriya 考案、先行研究情報求ム)
発想の原点は、挿入ソート→シェルソートやバブルソート→コムソートのように、比較や交換における最初の幅を大きくし、次第に小さくしていくプロセス。
「奇数要素と後続の偶数要素比較交換」「偶数要素と後続の奇数要素との比較交換」で1ステップとする。
初期の交換幅を、要素数以上のn(n+1)/2(※三角数)を与えるnのうち最小のnを選び、1ステップごとに交換幅を2ずつ狭める。
交換幅が1になったら、通常の奇遇転置ソートに切り替える。最初の交換幅が大きい分、ソートまでの時間が劇的に速くなるが、安定ソートではなくなる。
奇数幅で幅を狭める奇遇転置ソートを逐次処理に切り替えてシミュレート。
奇遇転置ソートをカスタマイズ。(K.Mikuriya 考案、先行研究情報求ム)
発想の原点は、挿入ソート→シェルソートやバブルソート→コムソートのように、比較や交換における最初の幅を大きくし、次第に小さくしていくプロセス。
「奇数要素と後続の偶数要素比較交換」「偶数要素と後続の奇数要素との比較交換」で1ステップとする。
初期の交換幅を、要素数未満のメルセンヌ数(※2のべき乗-1)を取り、数ステップごとに交換幅をメルセンヌ数に従って減らす。
交換幅を減らすステップ数は、要調整。1ステップずつだといくらか取り残される要素が出てソートが遅くなる。
交換幅が1になったら、通常の奇遇転置ソートに切り替える。最初の交換幅が大きい分、ソートまでの時間が劇的に速くなるが、安定ソートではなくなる。
メルセンヌ数で幅を狭める奇遇転置ソートを逐次処理に切り替えてシミュレート。
二つのソート済み列の結合を並列化に特化させたもの
同じ添字(変数)に対し「小の値」「大の値」となる二つのソート列をそれぞれ半分に分割し、
隣り合った小ソート列の同じ添字(変数)に対し「小の値」「大の値」となるように比較交換をする。
このような操作を行うことで、ソート中にできるソート列群の「先頭要素列」と「末尾要素列」が常に昇順になるように分割される。
ソート列は有限な為、分割を繰り返すことで必ず小ソート列の要素が1に到達し、上記の大小関係の性質によりソートが完了する。
「奇遇」は、このソートの分割統治法実装において、「奇数列と偶数列に分割」する処理があることが由来と思われる。
2の冪乗の要素数のソート列をマージしていくアルゴリズムだが、比較交換において逆順に交換することがない。
そのため、範囲外の要素との比較を無視することで、仮想的に2の冪乗要素数の初期配列とみなして適用できる。
特徴は、ソート結合中に「段々のソート列」ができること。
バッチャー奇遇マージソートを逐次処理に切り替えてシミュレート。
ソート対象をブロック単位で視覚化しています。
分割と併合の二つのステージを持つ。
分割ステージの際には数列単位で互いに大小関係を持った2数のソート列に分割する
その際、小ソート列内の要素は隣接せず、最終的に「要素数/2」の間隔を空けた数列になる。
併合ステージでは二つの小ソート列に「要素を交互に併合」・「整列」を繰り返し、全体をソートする。
その際、分割ステージで残した大小関係を利用して並列化可能なソートを行う。
ペアワイズとは、「対の要素同士」という意味。
2の冪乗の要素数の数列をソートするアルゴリズムだが、比較交換において逆順に交換することがない。
そのため、範囲外の要素との比較を無視することで、仮想的に2の冪乗要素数の初期配列とみなして適用できる。
特徴は、ソート結合中に「複数のソート列」が見え、それが挟み撃ちのごとく収束する様。
ペアワイズソーティングネットワークを逐次処理に切り替えてシミュレート。
ソート対象をブロック単位で視覚化しています。
最初は「奇数幅で幅を狭める奇遇転置ソート」を大雑把なソートを行い、
交換幅が1になってほとんどソート済みになったらノームソートで仕上げる。
逐次ソートにおいては、奇遇転置ソートより速い。