|
バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は Ken Batche(:en:Ken Batcher) によって考案された、要素数nに対して、大きさ O(''n'' (log ''n'')2) かつ深さ O((log ''n'')2) のソーティングネットワークである。これは漸近的に最適（:en:asymptotically optimal algorithm）ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、Batcheの方法のほうが (AKSネットワークよりも) 優れている。」と言った。〔D.E. Knuth. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.〕 the second GPU Gems book〔https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html〕の中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。 == Pythonによる実装例 == 入力として、2の累乗の長さを持ったリストを取り、ソート済みリストを返す。 def compare_and_swap(x, a, b): if x > x: x, x = x, x def oddeven_merge(x, lo, hi, r): step = r * 2 if step < hi - lo: oddeven_merge(x, lo, hi, step) oddeven_merge(x, lo + r, hi, step) for i in range(lo + r, hi - r, step): compare_and_swap(x, i, i + r) else: compare_and_swap(x, lo, lo + r) def oddeven_merge_sort_range(x, lo, hi): """ 区間lo と hiのソートを行う。 注意: 端点 (lo と hi) は含むものとする。 """ if (hi - lo) >= 1: # ひとつ以上の要素があった場合、入力を # 長さの半分で前後に分割し、 # その後それぞれをマージソートする。 mid = lo + ((hi - lo) / 2) oddeven_merge_sort_range(x, lo, mid) oddeven_merge_sort_range(x, mid + 1, hi) oddeven_merge(x, lo, hi, 1) def oddeven_merge_sort(x): oddeven_merge_sort_range(x, 0, len(x)-1) >>> data = 4, 3, 5, 6, 1, 7, 8 >>> oddeven_merge_sort(data) >>> data 2, 3, 4, 5, 6, 7, 8 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「バッチャー奇偶マージソート」の詳細全文を読む スポンサード リンク
|