Haskellでやると書いておいて、Pythonでやっちゃう罠。
Pythonがサポートしている中途半端な継続ことgeneratorでsortすれば、遅延評価と同じく、「先頭n個だけ使う」という用途では後半のsortを実行しないで済む。
>>> l = [3,5,2,1,4,5,8,2] >>> def lazy_sort(lst): if len(lst) == 0: return mid = lst[0] left = [] right= [] for v in lst[1:]: if v < mid: left.append(v) else: right.append(v) lg = lazy_sort(left) for y in lg: yield y yield mid rg = lazy_sort(right) for y in rg: yield y >>> s = lazy_sort(l) >>> s.next() 1 >>> s.next() 2 >>> s = lazy_sort(l) >>> list(s) [1, 2, 2, 3, 4, 5, 5, 8]
読んだら判ると思うけど、再帰しようとしたら自分がgeneratorだったから、再帰するたびに一旦generatorを作っている。Pythonのインタプリタがどう実行するのかイマイチ理解していないが、よっぽど凄い最適化をしてくれない限りは非常に効率が悪そう。
最初から再帰をしないで書くのが正攻法だろうけど、クイックソートって再帰で書きたくなるよね。