Python でリスト内包表記を使ってクイックソート

リスト内包表記の書き方がわかったので、これを使ってクイックソートを書いてみる。クイックソートと言えば、はじめて C で書いたときはちょっとしたミスで、エラーでまくりで嫌になったもんだ。そういえば, VB でも Java の真似して、ソートのためのインターフェイスを implement してクイックソート書いた覚えもあるなぁ  ^^;

 

クイックソートとは

クイックソート - Wikipedia によると、アルゴリズムは、

1. 適当な数（ピボットという）を選択する （この場合はデータの総数の中央値が望ましい）
2. ピボットより小さい数を前方、大きい数を後方に移動させる （分割）
3. 二分割された各々のデータを、それぞれソートする

こうやってみると、なんてシンプルなんだ。。。(@_@;)

 

Haskell でクイックソート

About Haskell の「クイックソート」では、

    qsort []     = []
    qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                     where
                       elts_lt_x   = [y | y <- xs, y < x]
                       elts_greq_x = [y | y <- xs, y >= x]

アルゴリズムが素直に表現されていてわかりやすい。

 

Python で書いてみる

Haskell のコードを真似して、

def qsort(list):
    if list == []: return []
    else:
        p = list.pop(0)
        return qsort([x for x in list if x < p]) + \
                [p] + \
                qsort([x for x in list if x >= p])

うーむ、簡潔に書けるものだ。 ^^

では、同じように、 Ruby でも、

def qsort(list)
    if list.empty? then return [] 
    else
        p = list.shift
        return qsort(list.select{|x| x < p}) + 
               [p] + 
               qsort(list.select{|x| x >= p})
    end
end

 

参考

リストの操作については、

• 5.1 リスト型についてもう少し

一文を複数行へ分ける方法は、

• 2.1.5 明示的な行継続