M.Hiroi's Home Page

Algorithms with Python

整列 (sorting) [2]

[ PrevPage | Python | NextPage ]

はじめに

整列 (sorting) の続きです。今回はヒープソート、マージソート、分布数えソート、基数ソート (直接基数法と基数交換法) について説明します。

●ヒープソート

ヒープ (heap) は 二分木とヒープ で説明したデータ構造です。実は、このヒープを使ったソートも優秀なアルゴリズムの一つです。実行時間は N * log2 N に比例しますが、平均するとクイックソートよりも遅くなります。しかし、クイックソートとは違って、データの種類によって性能が劣化することはありません。

プログラムは次のようになります。

リスト : ヒープソート

def heap_sort(buff):
    # ヒープの構成
    size = len(buff)
    for i in range(size // 2 - 1, -1, -1):
        n = i
        x = buff[n]
        while True:
            c = 2 * n + 1
            if c >= size: break
            if c + 1 < size and buff[c] < buff[c + 1]: c += 1
            if x >= buff[c]: break
            buff[n] = buff[c]
            n = c
        buff[n] = x
    # 最大値を取り出す
    for i in range(size - 1, -1, -1):
        x = buff[i]
        buff[i] = buff[0]
        n = 0
        while True:
            c = 2 * n + 1
            if c >= i: break
            if c + 1 < i and buff[c] < buff[c + 1]: c += 1
            if x >= buff[c]: break
            buff[n] = buff[c]
            n = c
        buff[n] = x

前半部分でヒープを構築します。親子関係が 二分木とヒープ の説明と逆になっていることに注意してください。つまり、親が子より大きいという関係を満たすようにヒープを構築します。したがって、配列の先頭 (buff[0]) が最大値になります。

後半部分で、最大値を取り出してヒープを再構築します。配列の先頭には最大値がセットされているので、これを配列の最後尾のデータと交換します。あとは、そのデータを除いた範囲でヒープを再構築すれば、その次に大きいデータを求めることができます。これを繰り返すことで、大きいデータが配列の後ろから整列していくことになります。

最初の for ループで、配列の前半部分のデータを後ろから順番に取り出します。次の while ループで、親子関係を満たすように修正します。変数 n が親の位置を、変数 c が子の位置を示します。次に、後半の for ループで、最大値 buff[0] と最後尾のデータ buff[i] を交換します。そして、while ループでヒープの再構築を行います。あとはヒープのプログラムとほとんど同じですが、ヒープを再構築する範囲が変数 i で管理されていて、その値は一つずつ減っていくことに注意してください。

それでは実行結果を示します。

  表 : ヒープソート (単位 : 秒)

 個数: 乱数  : 昇順  : 逆順  : 山型
-----+-------+-------+-------+-------
 1000: 0.002 : 0.003 : 0.004 : 0.002 
 2000: 0.005 : 0.007 : 0.005 : 0.005 
 4000: 0.017 : 0.022 : 0.011 : 0.021 
 8000: 0.037 : 0.035 : 0.022 : 0.024 
16000: 0.073 : 0.086 : 0.048 : 0.068 
32000: 0.169 : 0.156 : 0.139 : 0.144 
64000: 0.266 : 0.279 : 0.226 : 0.279 

実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

このように、ヒープソートはどのデータに対しても、そこそこの速度でソートすることができます。ただし、実行時間はクイックソートよりも遅くなりました。参考文献 [3] によると、ヒープソートの速度はクイックソートの半分くらいといわれています。ヒープソートの処理内容はクイックソートよりも複雑なので、時間がかかるのは仕方がないところでしょう。

●マージソート

マージ(併合 : merge)とはソート済みの複数の列を一つの列にまとめる操作のことです。このマージを使ったソートを「マージソート (merge sort)」といいます。最初にマージについて簡単に説明します。次の図を見てください。

2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。 a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。当たり前だと思われるでしょうが、これがマージソート (merge sort) の原理です。次の図を見てください。

  9 5 3 7 6 4 2 8   最初の状態

 |5 9|3 7|4 6|2 8|  長さ2の列に併合

 |3 5 7 9|2 4 6 8|  長さ4の列に併合 

  2 3 4 5 6 7 8 9   ソート終了

        図 2 : マージソート

マージをソートに応用する場合、最初は各要素をソート済みの配列 (リスト) として考えます。この状態で隣の配列とマージを行い、長さ 2 の配列を作ります。次に、この配列に対して再度マージを行い、長さ 4 の配列を作ります。このように順番にマージしていくと、最後には一つの配列にマージされソートが完了します。

それではプログラムを作りましょう。配列の長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。マージは 2 つの列を一つの列にまとめる操作です。そこで、まずソートする配列を 2 つに分けて、前半部分をソートします。次に後半部分をソートして、その結果をマージすればいいわけです。

では、どうやってソートするのかというと、再帰呼び出しするのです。そうすると、どんどん配列を 2 つに割っていくことになり、最後にデータが一つとなります。それはソート済みの配列と考えることができるので、再帰呼び出しを終了してマージ処理に移ることができます。あとはデータを順番にマージしていってソートが完了します。

プログラムは次のようになります。

リスト : マージソート

# 挿入ソート
def insert_sort1(buff, low, high):
    for i in range(low + 1, high + 1):
        temp = buff[i]
        j = i - 1
        while j >= low and temp < buff[j]:
            if temp >= buff[j]: break
            buff[j + 1] = buff[j]
            j -= 1
        buff[j + 1] = temp

# マージソート
def merge_sort(buff, low, high):
    if high - low <= LIMIT:
        insert_sort1(buff, low, high)
    else:
        mid = (low + high) // 2
        merge_sort(buff, low, mid)
        merge_sort(buff, mid + 1, high)
        #
        p = 0
        i = low
        while i <= mid:
            work[p] = buff[i]
            p += 1
            i += 1
        i = mid + 1
        j = 0
        k = low
        while i <= high and j < p:
            if work[j] <= buff[i]:
                buff[k] = work[j]
                k += 1
                j += 1
            else:
                buff[k] = buff[i]
                k += 1
                i += 1
        while j < p:
            buff[k] = work[j]
            k += 1
            j += 1

def msort(buff):
    global work
    work = [0] * (len(buff) // 2)
    merge_sort(buff, 0, len(buff) - 1)

最初に区間の幅が LIMIT 以下になったかチェックします。そうであれば、挿入ソート (insert_sort1) に切り替えてソートします。この方が少しですが速くなります。これが再帰呼び出しの停止条件になります。区間の幅が LIMIT よりも大きい場合はマージソートを行います。

まず列の中央を求めて変数 mid にセットします。最初に前半部、それから後半部をマージソートします。これは merge_sort() を再帰呼び出しするだけです。再帰呼び出しから戻ってくると、配列の前半部分と後半部分はソートされているのでマージ処理を行います。

まず前半部分を作業領域 work に退避します。work はグローバル変数として定義します。work の大きさはソートする配列の半分で十分です。たとえば、前半部分のデータよりも後半部分のデータがすべて小さいとします。この場合、後半部分のデータが先頭から順番にセットされ、その後ろに退避した前半部分のデータがセットされます。逆に、前半部分のデータがすべて小さければ、後半部分のデータは移動する必要はないので、work に退避した前半部分のデータを元に戻すことになります。

次の while ループで、前半部分もしくは後半部分どちらかにデータがある間、データの比較と移動を繰り返し行います。前半部分と後半部分を先頭から順番に比較し、小さい方を区間の先頭から順番にセットしていきます。後半部分のデータが先になくなって、作業領域 work にデータが残っている場合は、最後の while ループでデータを後ろに追加します。

それでは実行結果を示します。

  表 : マージソート (単位 : 秒)

 個数: 乱数  : 昇順  : 逆順  : 山型
-----+-------+-------+-------+-------
 1000: 0.003 : 0.001 : 0.002 : 0.002 
 2000: 0.005 : 0.003 : 0.005 : 0.004 
 4000: 0.013 : 0.006 : 0.011 : 0.008 
 8000: 0.033 : 0.020 : 0.037 : 0.017 
16000: 0.051 : 0.027 : 0.050 : 0.037 
32000: 0.124 : 0.063 : 0.114 : 0.102 
64000: 0.277 : 0.141 : 0.260 : 0.174 

実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

マージソートの実行時間は、要素数を N とすると平均して N * log2 N に比例します。マージソートはクイックソートと同様に高速なアルゴリズムですが、実際にプログラムを作って比較してみるとクイックソートの方が高速です。しかし、マージソートは配列を単純に二分割していくため、クイックソートと違ってデータの種類によって性能が劣化することはありません。ヒープソートと同様に、どのようなデータに対しても力を発揮してくれるわけです。ただし、ヒープソートとは違って作業領域が必要になります。

なお、マージソートは連結リストのソートや外部ソートに適したアルゴリズムです。連結リストのソートは次回に取り上げることにしましょう。

●マージソートの改良

マージソートは、配列 buff の大きさを N とすると、大きさが N / 2 の作業用領域 work を必要としました。ここで、作業領域 work の大きさを配列 buff と同じ N にすることを考えます。この場合、最初に buff を work にコピーしておいて、再帰のたびに buff と work を交互に入れ換えることで、マージソートの実行速度を改善することができます。

なお、この方法は C++によるソート(sort)のページ 修正マージソート を参考にさせていただきました。同ページによると、『修正マージソートは、Java のクラス型のソートに採用されています。』 とのことです。有用な情報を公開されている作者様に感謝いたします。

プログラムは次のようになります。

リスト : 改良版マージソート

def merge_sort1(a, b, low, high):
    if high - low <= LIMIT:
        insert_sort1(b, low, high)
    else:
        mid = (low + high) // 2
        merge_sort1(b, a, low, mid)
        merge_sort1(b, a, mid + 1, high)
        i = low
        j = mid + 1
        k = low
        while i <= mid and j <= high:
            if a[i] <= a[j]:
                b[k] = a[i]
                i += 1
            else:
                b[k] = a[j]
                j += 1
            k += 1
        while i <= mid:
            b[k] = a[i]
            k += 1
            i += 1
        while j <= high:
            b[k] = a[j]
            k += 1
            j += 1

def msort1(buff):
    work = buff[:]
    k = len(buff)
    merge_sort1(work, buff, 0, k - 1)

msort1() は buff をコピーした配列 work を生成し、それを merge_sort1() に渡してマージソートします。merge_sort1(a, b, low, high) は、配列 b の区間 (low, high) を二分割してソートします。merge_sort1() を再帰呼び出しするとき、引数 a, b を逆にすることに注意してください。

二つの区間をソートしたあと、二つの区間をマージした結果は配列 a の区間 (low, high) にセットします。改良前の merge_sort() では、あらかじめ buff の前半部分を work に退避していましたが、buff を work にコピーしておいて、buff と work を交互に切り替えることで、buff の前半部分を work に退避する処理が不要になります。

それでは実行結果を示します。

  表 : 改良版マージソート (単位 : 秒)

 個数: 乱数  : 昇順  : 逆順  : 山型
-----+-------+-------+-------+-------
 8000: 0.022 : 0.015 : 0.017 : 0.015
16000: 0.053 : 0.034 : 0.036 : 0.032
32000: 0.113 : 0.062 : 0.098 : 0.076
64000: 0.200 : 0.150 : 0.168 : 0.161

実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

結果を見ればお分かりのように、昇順データ以外では改良版のほうが速くなりました。改良の効果は十分に出ていると思います。メモリを多く使用することになりますが、このような簡単な方法でマージソートを改良できるとは驚きました。

●基数ソート

今まで説明したソートは、要素を比較して適切な位置に移動することでソートを行ってきました。ところが、要素の性質によっては比較しなくてもソートすることができます。たとえば、トランプの札をソートすることを考えてみましょう。手作業で行う場合、1 の札はここ、2 の札はここ、3 の札はここ、というように置く場所を決めて札を分けていきます。そして、最後に 1 の札から順番に並べればソートが済んだことになります。

一般には、要素のキーの種類だけ入れ物(ビン)を用意して、要素をキーに対応するビンに入れていきます。キーはソートしようとする要素の性質を表します。トランプでいえば、1 から 13 という数字のことです。区分けが終了したらキーの小さい方からビンの内容を出力すればソートが完了することになります。これを「ビンソート (bin sort)」とか「バケットソート (bucket sort)」といいます。ビンソートの実行時間は要素数に比例します。

ビンソートを行う場合、キーの種類が限られた有限の値でなければソートすることはできません。トランプの場合、札が 1 から 13 までという限られた値しかないので簡単にソートすることができたのです。ここでは、ビンには複数のデータを入れることができるものとします。キーの種類がたくさんある場合はビンソートを簡単に使うことはできません。ところが、キーの特性をうまく使えば、種類がたくさんあってもビンソートを応用することができます。

簡単な例を示しましょう。2 桁の 10 進数をソートします。0 から 99 までの 100 個のビンは用意できないが、0 から 9 の 10 個のビンならば用意できると仮定します。現実的な話ではありませんが、説明のためということでご了承ください。もうおわかりかもしれませんが、1 の位と 10 の位の 2 回に分けてビンソートを行えば、全体をソートすることができます。これを「基数ソート (radix sort)」といいます。次の図を見てください。

  21 5 34 8 1 13 2 89 3 55

  (1) 1 の位で分ける
  ビン
  [0] :          [5] : 5 55
  [1] : 21  1    [6] :
  [2] :  2       [7] :
  [3] : 13  3    [8] :  8
  [4] : 34       [9] : 89

  21 1 2 13 3 34 5 55 8 89

  (2) 10 の位で分ける
  ビン
  [0] :  1 2 3 5 8 [5] : 55
  [1] : 13         [6] :
  [2] : 21         [7] :
  [3] : 34         [8] : 89
  [4] :            [9] :

  1 2 3 5 8 13 21 34 55 89  ソート完了

        図 3 : 基数ソート

まず 1 の位でビンソートを行ないます。順番にビンに入れていくので、ビンのなかの整数の順序はビンに入れる前の順序と同じです。ビンから取り出して並べると、1 の位でソートされた状態になります。ビンから取り出すときも、最初に入れた要素から取り出していくことに注意してください。。

次に 10 の位でビンソートを行ないます。すでに 1 の位でソートされているので、各ビンには小さい順番で整数が並んでいきます。最後に小さいビンから出力すればソートが完了します。

●分布数えソート

それでは、具体的にどのようにプログラムすればよいのでしょうか。ビンのサイズはデータを調べてみないとわかりません。連結リストなどのデータ構造を使ってビンを実現することもできますが、もっと単純な方法があります。それは「度数分布表」を使う方法です。この方法を「分布数えソート (distribution counting sort)」といいます。

度数分布表とはキーの要素数を数え上げた表のことです。そして、度数分布表の左から右へ要素を順番に足し合わせたものを「累積度数表」といいます。この表を使うと要素を順番に並べることができます。先ほどの例をあてはめてみましょう。まず、1 の位に対しての度数分布表を作ります。

  21 5 34 8 1 13 2 89 3 55

  度数分布表
     0  1  2  3  4  5  6  7  8  9
 T1[ 0  2  1  2  1  2  0  0  1  1 ]


    図 4 : 度数分布表の作成

この表を作るのは簡単ですね。1 の位を配列の添字に対応させて、対応する配列の要素を 1 増やしていくだけです。もちろん、配列の要素は 0 に初期化しておくことをお忘れなく。次は累積度数表に変換します。これも簡単で、添字 0 から順番に足していくだけです。

   累積度数表に変換

     0  1  2  3  4  5  6  7  8  9
 T2[ 0  2  3  5  6  8  8  8  9  10 ]


    図 5 : 累積度数表の作成

この表は 0 からそのキーまでの要素の合計数を表しています。したがって、1 の位が n のデータは、配列の (T2[n] - T1[n]) 番目から (T2[n] - 1) 番目に配置されることになります。たとえば、1 の位が 5 の場合、T1[5] = 2, T2[5] = 8 なので、6, 7 番目に配置されます。そこで、作業用の配列を用意して累積度数表の示す位置にデータを配置していけば、1 の位でソートしたことになります。次の図を見てください。

作業用配列には、ソート前の配列の後ろ側からデータを取り出してセットしていきます。これは、同じ値が複数ある場合、その順番を変えないようにするためです。そうしないと、基数ソートは動作しません。また、これで基数ソートは安定なソートになります。

データは T2[n] - 1 の位置にセットし、そのあとで T2[n] の値を一つ減らします。そうしないと、複数の値があると同じ位置に書き込んでしまいます。プログラムでは、T2[n] の値を -1 (T2[n] -= 1) してから、その位置にデータを書き込めばいいわけです。

次に、10 の位に対して同様に分布数えソートを行えば基数ソートは完了します。下図を参考にしてください。

このように、下位の桁 (右の桁) からソートしていく方法を「直接基数法 (straight radix sort)」と呼びます。逆に、上位の桁 (左の桁) からソートしていく方法もあります。これを「基数交換法 (radix exchange sort)」と呼びます。最下位桁 (Least Significant Digit) を LSD, 最上位桁 (Most Significant Digit) を MSD と呼ぶことから、LSD radix sort, MSD radix sort と呼ぶ場合もあります。基数交換法についてはあとで詳しく説明します。

●直接基数法

それでは、基数ソート (直接基数法) のプログラムを作りましょう。ここでは、整数値の範囲を 0 から 4294967295 (32 bit 無符号整数) に限定します。この場合、10 進数では 10 桁になりますが、256 進数で考えると 4 桁と少なくなります。また、各桁の値はビット操作で簡単に求めることができるので便利です。

プログラムは次のようになります。

リスト : 基数ソート (直接基数法)

def radix_sort(buff):
    size = len(buff)
    work = [0] * size
    count = [0] * 256

    for i in range(4):
        shift = i * 8
        for x in range(256): count[x] = 0
        for x in range(size):
            count[(buff[x] >> shift) & 0xff] += 1
        for x in range(1, 256):
            count[x] += count[x - 1]
        for x in range(size - 1, -1, -1):
            y = (buff[x] >> shift) & 0xff
            count[y] -= 1
            work[count[y]] = buff[x]
        temp = buff
        buff = work
        work = temp

基数ソートはマージソートと同様に作業用の配列が必要になります。ここでは、buff と同じサイズの配列 work を用意します。度数分布表と累積度数表は配列 count を使って作成します。count の大きさは 256 になります。

次に、for ループで下位の桁から分布数えソートを行います。変数 shift はビットシフト用の変数で、0, 8, 16, 24 と 8 ビットずつ増やしていきます。まず最初に、count を 0 に初期化します。そして、次の for ループで度数分布表を作成します。取り出す桁に合わせて右ビットシフトして 0xff とアンドをとれば、その桁の値を求めることができます。それから、count の要素を加算して累積度数表を作成します。これも簡単ですね。

最後の for ループで、累積度数表の示す位置にデータをセットします。このとき、最初に累積度数表の値をデクリメントしておくことをお忘れなく、すべてのデータをセットしたら、work と buff を交換します。あとはこれを 4 回繰り返すだけです。交換する回数は偶数なので、ソートされたデータは引数として渡された配列にセットされます。

それでは実行結果を示します。

  表 : 基数ソート (単位 : 秒)

 個数: 乱数  : 昇順  : 逆順  : 山型
-----+-------+-------+-------+-------
 1000: 0.002 : 0.002 : 0.001 : 0.001 
 2000: 0.003 : 0.004 : 0.003 : 0.003 
 4000: 0.010 : 0.005 : 0.008 : 0.006 
 8000: 0.011 : 0.025 : 0.013 : 0.011 
16000: 0.034 : 0.028 : 0.021 : 0.029 
32000: 0.057 : 0.042 : 0.058 : 0.042 
64000: 0.124 : 0.096 : 0.098 : 0.092 

実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

乱数データと山型データの場合、基数ソートの方がクイックソートよりも速くなりました。とくに、データ数が多くなると、その差が大きくなります。

キーを m 個に分割した場合、基数ソートは分布数えソートを m 回繰り返し実行する必要があります。したがって、要素数を n とすると実行時間は m * n に比例します。しかし、m が n に比べて十分に小さい場合は、基数ソートの実行時間は n に比例すると考えることができます。実際、今回の実行結果を見ると、要素数が 2 倍になると実行時間も約 2 倍になっていることがわかります。

●基数交換法

次は基数交換法のプログラムを作りましょう。基数交換法は上位の桁からソートしますが、この場合は再帰呼び出しを使うと簡単です。次の図を見てください。

最初に 10 の位で分布数えソートします。すると、10 の位が等しいデータが集まるので、次は等しいデータの区間を 1 の位で分布数えソートします。上図の場合、0 のデータが 0 番目から 4 番目の範囲にあります。今度は区間 (0, 4) にあるデータを 1 の位で分布数えソートします。この処理は再帰呼び出しを使うと簡単に実現できます。10 の位が 1, 2, 3, 5, 8 のデータは 1 つしかないので、1 の位でソートする必要はありません。

プログラムは次のようになります。

リスト : 基数ソート (基数交換法)

def radix_sort1(buff, low, high, n = 3):
    if high - low <= LIMIT:
        insert_sort1(buff, low, high)
    else:
        count = [0] * 257
        shift = n * 8
        for i in range(low, high + 1):
            count[(buff[i] >> shift) & 0xff] += 1
        for i in range(1, 256):
            count[i] += count[i - 1]
        for i in range(high, low - 1, -1):
            c = (buff[i] >> shift) & 0xff
            count[c] -= 1
            work[count[c] + low] = buff[i]
        for i in range(low, high + 1):
            buff[i] = work[i]

        if n > 0:
            count[256] = high - low + 1
            for i in range(0, 256):
                l = low + count[i]
                h = low + count[i + 1] - 1
                if l < h: radix_sort1(buff, l, h, n - 1)

def rsort1(buff):
    global work
    work = [0] * len(buff)
    radix_sort1(buff, 0, len(buff) - 1)

関数 radix_sort1() の引数 low, high がソートする区間を表します。引数 n が分布数えソートを行う桁数を表します。区間 (low, high) が LIMIT (10) よりも小さい場合は挿入ソート (insert_sort1) に切り替えます。この方が少しですが速くなります。そうでなければ、分布数えソートを行います。これは今までとほとんど同じですが、区間が (low, high) であることと、ソートしたあとで work から buff へデータをコピーしているところが違います。ご注意ください。

最後に、n が 0 より大きい場合は、次の桁をソートするため radix_sort1() を再帰呼び出しします。桁の値 (0 - 255) を i とすると、その区間は low + count[i] から low + count[i + 1] - 1 までになります。count は累積度数表ですが、データをセットするときにデクリメントされていくため、count[i] は区間の始点に、count[i + 1] - 1 は区間の終点になることに注意してください。

それでは実行結果を示します。

  表 : 基数交換法 (単位 : 秒)

 個数: 乱数  : 昇順  : 逆順  : 山型
-----+-------+-------+-------+-------
 1000: 0.002 : 0.002 : 0.002 : 0.002 
 2000: 0.004 : 0.005 : 0.004 : 0.004 
 4000: 0.014 : 0.010 : 0.007 : 0.012 
 8000: 0.026 : 0.016 : 0.014 : 0.014 
16000: 0.046 : 0.029 : 0.028 : 0.027 
32000: 0.080 : 0.068 : 0.063 : 0.072 
64000: 0.132 : 0.113 : 0.117 : 0.125 

実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

直接基数法よりも少し遅くなりましたが、山型データはクイックソートよりも速くなりました。ところで、基数交換法 (MSD radix sort) は文字列のソートにも応用することができます。これは次回で取り上げることにしましょう。

●2進基数交換法

ところで、基数交換法は 2 進数を基準に行うこともできます。これを「2進基数交換法」といいます。2 進数で考えると、桁の値は 0 と 1 しかありません。ビットが 0 のデータを前半に、ビットが 1 のデータを後半に分割していけば、データをソートすることができます。データの分割はクイックソートと同様に、左から 1 のデータを探し、右から 0 のデータを探して、それを交換することで実現できます。したがって、今までの基数ソートとは違って、作業用のメモリ領域は必要ありません。そのかわり、2進基数交換法は不安定なソートになります。

プログラムは次のようになります。

リスト : 基数ソート (2 進基数交換法)

def radix_sort2(buff, low, high, n = 0x80000000):
    if high - low <= LIMIT:
        insert_sort1(buff, low, high)
    else:
        i = low
        j = high
        while True:
            while i <= j and buff[i] & n == 0: i += 1
            while i <= j and buff[j] & n > 0: j -= 1
            if i > j: break
            temp = buff[i]
            buff[i] = buff[j]
            buff[j] = temp
            i += 1
            j -= 1
        if n > 1:
            radix_sort2(buff, low, j, n >> 1)
            radix_sort2(buff, i, high, n >> 1)

def rsort2(buff):
    radix_sort2(buff, 0, len(buff) - 1)

関数 radix_sort2() の引数 low, high がソートする区間を表します。引数 n がチェックするビットを表します。区間 (low, high) が LIMIT (10) よりも小さい場合は挿入ソート (insert_sort1) に切り替えます。この方が少しですが速くなります。そうでなければ、区間 (low, high) をビット 0 と 1 で二分割します。

分割方法はクイックソートとほとんど同じです。2 番目の while ループで、左側からビット 1 の要素を探します。ここではビットが 0 の間は探索位置を進める、というように置き換えています。同様に次の while ループで右側からビット 0 の要素を探します。クイックソートとは違って、i <= j のチェックが必要なことに注意してください。お互いの探索位置 i と j が交差したら分割は終了です。break 文で while ループから脱出します。そうでなければお互いの要素を交換します。あとは、分割した区間に対して radix_sort2() を再帰呼び出しするだけです。

それでは実行結果を示します。

  表 : 2進基数交換法 (単位 : 秒)

 個数: 乱数  : 昇順  : 逆順  : 山型
-----+-------+-------+-------+-------
 1000: 0.004 : 0.004 : 0.004 : 0.005 
 2000: 0.007 : 0.010 : 0.008 : 0.010 
 4000: 0.016 : 0.017 : 0.014 : 0.017 
 8000: 0.039 : 0.033 : 0.026 : 0.037 
16000: 0.082 : 0.052 : 0.051 : 0.067 
32000: 0.145 : 0.116 : 0.116 : 0.161 
64000: 0.267 : 0.228 : 0.281 : 0.299 

実行環境: Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

実行速度は分布数えソートを使った基数交換法 (radix_sort1) やクイックソートよりもずいぶんと遅くなりました。ビット操作が得意なC言語を使うと、もう少し速くなるかもしれません。


初版 2006 年 12 月 30 日
改訂 2022 年 9 月 3 日

Copyright (C) 2006-2022 Makoto Hiroi
All rights reserved.

[ PrevPage | Python | NextPage ]