メディアンソート

久しぶりの投稿!VPN サーバーは一体どうなった!?実を言うと、実験に使えるマシンがなくなってしまったので、続編はすぐに書けない状況です(ひどい)…。L2TP over IPsec + NAT トラバーサルで外出先から iPhone を NAT された社内 IPsec サーバーを経由して社内ネットワークにつなげちゃう!みたいなことを、フリーソフトウェアだけで簡単に実現できるのか、僕も試してみたいんですけどね。

泣き事は置いといて、メディアンソートです!なにそれ!というのは後述するとして、以前経産省のソフトウェア何とかっていう試験を受ける時に初歩的なアルゴリズムをいくつも勉強した気がしますが、試験対策の丸暗記だったのでさっぱり記憶にありません。基本的なアルゴリズムを知らずに「僕はITエンジニアです」と自称するのは如何なものか、と懊悩すること度重なってきた(誇張)ので、精神の平安のために最近アルゴリズム体操を始めました。

O’Reilly の “Algorithms In a Nutshell” (日本語版はこれです。Amazon のアフィリエイトです。えへへ) を読んでまして、いよいよ具体的なアルゴリズムの段に来たんですが、件のメディアンソートがよく分からないんです…。よく分からないなら挙動を観察しよう、ということで以下の Python スクリプトを作りました:

#!/usr/bin/python
# coding:utf8

#import random

def median_sort(ary, left=0, right=None):
  def partition(ary, left, right, pivotIndex):
    pivot = ary[pivotIndex]
    ary[pivotIndex], ary[right] = ary[right], ary[pivotIndex]
    store = left

    for i in range(left, right):
      if cmp(ary[i], pivot) <= 0:
        ary[store], ary[i] = ary[i], ary[store]
        store += 1

    ary[store], ary[right] = ary[right], ary[store]
    return store

  def selectKth(ary, k, left, right):
    print
    print "selectKth: k=%d, left=%d, right=%d " % (k, left, right)
    print ary
    #i = int(random.random() * (right - left + 1)) + left
    i = left
    pivotIndex = partition(ary, left, right, i)
    print "pivotIndex=%d moved to %d by partitioning" % (i, pivotIndex)
    print ary

    if left + k - 1 == pivotIndex:
      print "left + k - 1 == pivotIndex"
      return pivotIndex

    if left + k - 1 < pivotIndex:
      print "left + k - 1 < pivotIndex"
      return selectKth(ary, k, left, pivotIndex)

    print "left + k - 1 > pivotIndex"
    return selectKth(ary, k - (pivotIndex - left + 1), pivotIndex + 1, right)

  if right == None:
    right = len(ary) - 1

  if left >= right:
    return

  mid = (right - left + 1) / 2
  me = selectKth(ary, mid + 1, left, right)
  median_sort(ary, left, left + mid - 1)
  median_sort(ary, left + mid + 1, right)

if __name__ == '__main__':
  ary = [15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14]
  median_sort(ary)

median_sort は配列の要素をソートする関数です。受け取った配列を直接操作します。戻り値はありません。

median_sort 関数の中に partition と selectKth というヘルパー関数があります。partition は配列の特定の範囲、もしくは全部を pivotIndex で指定した値 (pivot) 以下の要素を pivot の左に、それ以外の要素を pivot の右に来るように整理します。戻り値は pivot の新しいインデックスです。名前の通り配列を分割するイメージです。

わからないのが selectKth です。説明を読んでも、何してるのかさっぱり。そもそも英文が読めない、という説もありますが…。ということで、上のスクリプトを実行して観察してみました。

selectKth: k=9, left=0, right=15 
[15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14]
pivotIndex=0 moved to 14 by partitioning
[14, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 2, 10, 15, 16]
left + k - 1 < pivotIndex

selectKth: k=9, left=0, right=14 
[14, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 2, 10, 15, 16]
pivotIndex=0 moved to 13 by partitioning
[9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 2, 10, 14, 15, 16]
left + k - 1 < pivotIndex

selectKth: k=9, left=0, right=13 
[9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 2, 10, 14, 15, 16]
pivotIndex=0 moved to 8 by partitioning
[8, 1, 4, 7, 6, 5, 3, 2, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 == pivotIndex

selectKth: k=5, left=0, right=7 
[8, 1, 4, 7, 6, 5, 3, 2, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=0 moved to 7 by partitioning
[2, 1, 4, 7, 6, 5, 3, 8, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 < pivotIndex

selectKth: k=5, left=0, right=7 
[2, 1, 4, 7, 6, 5, 3, 8, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=0 moved to 1 by partitioning
[1, 2, 4, 7, 6, 5, 3, 8, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=3, left=2, right=7 
[1, 2, 4, 7, 6, 5, 3, 8, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=2 moved to 3 by partitioning
[1, 2, 3, 4, 6, 5, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=1, left=4, right=7 
[1, 2, 3, 4, 6, 5, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=4 moved to 5 by partitioning
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 < pivotIndex

selectKth: k=1, left=4, right=5 
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=4 moved to 4 by partitioning
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 == pivotIndex

selectKth: k=3, left=0, right=3 
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=0 moved to 0 by partitioning
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=2, left=1, right=3 
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=1 moved to 1 by partitioning
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=1, left=2, right=3 
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=2 moved to 2 by partitioning
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 == pivotIndex

selectKth: k=2, left=0, right=1 
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=0 moved to 0 by partitioning
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=1, left=1, right=1 
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=1 moved to 1 by partitioning
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 == pivotIndex

selectKth: k=2, left=5, right=7 
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=5 moved to 5 by partitioning
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=1, left=6, right=7 
[1, 2, 3, 4, 5, 6, 8, 7, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=6 moved to 7 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 < pivotIndex

selectKth: k=1, left=6, right=7 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=6 moved to 6 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 12, 13, 10, 11, 15, 16]
left + k - 1 == pivotIndex

selectKth: k=4, left=9, right=15 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 12, 13, 10, 11, 15, 16]
pivotIndex=9 moved to 13 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 10, 11, 14, 15, 16]
left + k - 1 < pivotIndex

selectKth: k=4, left=9, right=13 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 10, 11, 14, 15, 16]
pivotIndex=9 moved to 11 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=1, left=12, right=13 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
pivotIndex=12 moved to 12 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
left + k - 1 == pivotIndex

selectKth: k=2, left=9, right=11 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
pivotIndex=9 moved to 9 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=1, left=10, right=11 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
pivotIndex=10 moved to 10 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
left + k - 1 == pivotIndex

selectKth: k=2, left=13, right=15 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
pivotIndex=13 moved to 13 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
left + k - 1 > pivotIndex

selectKth: k=1, left=14, right=15 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
pivotIndex=14 moved to 14 by partitioning
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
left + k - 1 == pivotIndex

どうやら、 left ≤ k – 1 ≤ right となる k が pivotIndex より左にあれば [left, pivotIndex] の範囲で selectKth を、pivotIndex より右なら [pivotIndex+1, right] の範囲で selectKth を実行しているだけのようです。k -1 は配列全体に対する位置ではなくて [left, right] の範囲内での位置を示していること、言い換えると range(0, len(ary)) での k の位置 (k の絶対位置) は left + k – 1 であること。ここが重要のようです。なお、pivotIndex を決定するアルゴリズム、というのもあるようです。奥が深ーい。

結局、median_sort は最初に selectKth を実行して配列の中央値を探していた訳です (k に (配列の要素数 / 2) を渡しているので)。selectKth は partition を実行するので、配列が中央値以下とそれ以外の部分にキレイに分割されます。分割されて出来たサブアレイに対してまた median_sort をかけていくと、配列全体がソートされたことになる、ということのようです。いや、上記と同じことが本にちゃんと書いてあるんですが、上の実行結果を自分の目で見るまで理解できませんでした。やーねー。でも、left ≤ pivotIndex ≤ right ならどんな pivotIndex を選んでもいい、というのもよく分かりませんが…。

こうやって書いてみると、自分がとんでもないマヌケであることが痛感されます。試験勉強の時に使った教材ではすんなり理解できた気がするんですが…(確かこの本です。アフィ)。気のせいだったんでしょう。ともかくこんな本を買った以上、最後まで読みきらなきゃね!

(コウヅ)

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中