比較しないソートの作成 in Python DouKaku?

ソート対象のデータ同士で一切比較などを行わずにソートし、ソート結果を出力するプログラムを作成してください。条件は以下の通り。
・最低値・最大値・個数・並び替え対象の4つを引数として受け取る
・最大値と最低値はあくまで取りうる可能性であり、実際に出現することを保障するものではない。
・同値が複数出現することがある。
・入出力方法及びフォーマットは自由、関数として実装し引数に渡す形でも良い。
・小数点以下の数値が渡されることはないが、負の数は渡される可能性がある。
・最大値や最低値を元に算出した数値との比較は使用しても問題ありません。
・出来るだけ多様な条件のデータをソートできるアルゴリズムを使ってください(データが多少多いときや一定の並び順だとソート失敗するものはダメ)
・昇順降順はどちらでもかまいません

以下サンプル入出力
>>入力
-1 10 10
-1 9 4 8 9 6 3 9 5 2
>>出力
-1 2 3 4 5 6 8 9 9 9

これでいいのかな。

def sort(min, max, a):
    counts = [0] * (max - min + 1)
    for x in a:
        counts[x - min] += 1
    result = []
    for i, count in enumerate(counts):
        for _ in xrange(count):
            result.append(i + min)
    return result

def main():
    print sort(-1, 10, [-1, 9, 4, 8, 9, 6, 3, 9, 5, 2])

if __name__ == '__main__':
    main()

listを何回も作っているのがダサいです。アルゴリズムとしてはradix sort系です。

def nocmpsort(min, max, count, data):
  """
    >>> nocmpsort(min=-1, max=10, count=10,\
          data=[-1, 9, 4, 8, 9, 6, 3, 9, 5, 2])
    [-1, 2, 3, 4, 5, 6, 8, 9, 9, 9]
  """
  latitude = max - min
  base = 0
  x = 1
  while latitude > x:
    x = x << 1
    base += 1
  def encode(e):
    return e - min
  def decode(d):
    return d + min
  def nocmpsort_binary(data):
    """
    >>> base =  5
    >>> nocmpsort_binary([0, 10, 5, 9, 10, 7, 4, 10, 6, 3])
    [0, 3, 4, 5, 6, 7, 9, 10, 10, 10]
    """
    bin = list()
    for i in range( 2 << base):
      bin.append(0)
    for d in data:
      bin[d]+=1
    r = list()
    for i, count in enumerate(bin):
      while count > 0:
        r.append(i)
        count -=1
    return r

  return map(decode, nocmpsort_binary(map(encode, data)))

再帰をつかった基数2のバージョン

def nocmpsort(min, max, count, data):
  """
    >>> nocmpsort(min=-1, max=10, count=10,\
          data=[-1, 9, 4, 8, 9, 6, 3, 9, 5, 2])
    [-1, 2, 3, 4, 5, 6, 8, 9, 9, 9]
  """
  latitude = max - min
  base = 0
  x = 1
  while latitude > x:
    x = x << 1
    base += 1
  def encode(e):
    return e - min
  def decode(d):
    return d + min
  def nocmpsort_binary(data):
    """
    >>> base =  5
    >>> nocmpsort_binary([0, 10, 5, 9, 10, 7, 4, 10, 6, 3])
    [0, 3, 4, 5, 6, 7, 9, 10, 10, 10]
    """
    def binary(base, data):
      if base == -1:
        r = list(data)
        return r
      assert base > -1
      small = list()
      big = list()
      mask = 1 << base
      for d in data:
        if mask & d:
          big.append(d)
        else:
          small.append(d)
      r = binary(base - 1, small)
      r.extend(binary(base - 1, big))
      return r
    return binary(base, data)

  return map(decode, nocmpsort_binary(map(encode, data)))

if __name__ == "__main__":
  import doctest
  doctest.testmod()

DouKaku?

比較しないソートの作成

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq