一様乱数のソート
「区間[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