一様乱数のソート

区間[0,M)なるN個の一様乱数を昇順に配列に格納したい.M は十分に大きい.領域計算量O(N),時間計算量O(N)でこれを行う方法を考えよ.」という問題について、バケットソートを使って Python で書いてみた。

比較回数(適当だから間違ってるかも)は、1000個でやるとだいたい600〜700回になる。

バケットのソートには、Wikipediaの挿入ソートを使った。

import random, math

M = 2 ** 32
N = 1000

def insertion_sort(target_list):
  steps = 0
  for i in range(1, len(target_list)):
    steps += 1
    tmp = target_list[i]
    if target_list[i-1] > tmp:
      j = i
      while True:
        steps += 1
        target_list[j] = target_list[j-1]
        j -= 1
        if j <= 0 or target_list[j-1] <= tmp: break
      target_list[j] = tmp
  return steps

bucket = [[] for x in range(N)]
bucket_size = int(math.ceil(float(M) / N))
target_array = []

for i in range(N):
  r = random.randint(0, M-1)
  bucket[int(r / bucket_size)].append(r)

steps_all = 0
for i in range(N):
  steps_all += insertion_sort(bucket[i])
  target_array.extend(bucket[i])

print steps_all, target_array