ランダムソート(笑)とは - 西尾泰和のはてなダイアリー誰が「ソートするときに比較関数に『ランダムに1か-1を返す関数』を与えたらシャッフルできる」って言い出したのかしらないけど、真に受ける方も真に受ける方だと思う。 たとえばソート関数が下のような「リストの先頭の値をピボットにしてそれより大きいものと小さいものに振り分けるクイックソート」だったとする。比較関数の所はランダムにしてある。 >>> def quicksort(xs): from random import random if len(xs) < 2: return xs pivot = xs[0] left = [] right = [] for x in xs[1:]: if random() < 0.5: left.append(x) else: right.append(x) return quicksort(left) + [pivot] + quicksort(right
