孤独にそっくり

開いている窓の前で立ち止まるな

【アルゴリズム勉強その2】クイックソート

プログラミング

脈絡もなくクイックソート。その名前の通り、なんか早いらしい。再帰で書けるらしい。

クイックソート

クイックソート - Wikipedia
わかりやすいgifがある（英語wikiのほうがめちゃくちゃ情報量が多いけど読む気がしなかった）
Sorting algorithms/Quicksort - Rosetta Code
あとでコードを眺めるときに使う。擬似コードは読んでも分からない

特徴
  • データや並び方によってはそんな早くない
  • 安定ソートではない（交換するデータの組み合わせに依存するってこと？）
  • ピボットの選び方が問題

例を読んでいてひっかかったのは、ピボット自身を発見した時の挙動。

  • ピボット基準で、自分より小さいものが左にあるかチェック（あるいは自分を発見）
  • ピボット基準で、自分より大きいものが右にあるかチェック（あるいは自分を発見）
  • 入れ替え（自分を発見した場合は、自分を入れ替え）

みたいな。最初はピボットは動かさないのかと謎の勘違いをしていたせいで混乱した。

C

言語別に眺める。まずはC。

void quicksort(int *A, int len) {
  /* 配列の長さが1になったら終了*/
  if (len < 2) return;
  /* 配列の真ん中をピボットにする*/ 
  int pivot = A[len / 2];
 
  int i, j;
   /* iは左から数えた位置、jは右から数えた位置*/
   for (i = 0, j = len - 1; ; i++, j--) {
    /* 位置をずらして、ピボットと比較。*/
    while (A[i] < pivot) i++;
    while (A[j] > pivot) j--;
    /* i>=jだと終了。ピボットの位置が重なるか、交差した場合(1)*/
    if (i >= j) break;
    /* 値の入れ替え*/ 
    int temp = A[i];
    A[i]     = A[j];
    A[j]     = temp;
  }
  /* 前からi要素までを再帰*/ 
  quicksort(A, i);
  /* i番目以降からlen番目まで再帰*/
  quicksort(A + i, len - i);
}

なるほど。
違和感を覚えた個所は、(1)のところで実装されてる。

Python

def quickSort(arr):
    less = []
    pivotList = []
    more = []
    #配列の長さが1で終了
    if len(arr) <= 1:
        return arr
    else:
        #最初の値をpivotに
        pivot = arr[0]
        #pivotより小さかったらless、大きかったらmore、pivot自信はpivotList
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                more.append(i)
            else:
                pivotList.append(i)
        #再帰に投げる
        less = quickSort(less)
        more = quickSort(more)
        #値の入れ替えの代わり
        return less + pivotList + more

Pythonでは値の入れ替えをしないで、配列の長さが1になったら、再帰で一つ上の階層？にもどって、less + pivotList + moreを計算してる。
このとき、lessとmoreは必ずしもあるわけではない。
返り値はソート済みの配列になっていることを、足し算で表現している。面白いなあ。
Haskell風に書いてるやばいやつが載ってるけど、同じ要領でプログラムされてる。
Cで書かれていてわかりにくい部分が解消されていて、ストンと理解できて気持ちいい。
けど、再帰で分岐してるからよくわからないけど、厳密にquicksortなの？って気もする。

Common Lisp

(defun quicksort (list &aux (pivot (car list)) )
;;listの最初をpivotにする
;;&auxはlet的な働きをするパラメタらしい・・・？
  (if (cdr list)
  ;;pivot以外
      (nconc (quicksort (remove-if-not #'(lambda (x) (< x pivot)) list))
      ;;nconcはリストの結合
      ;;remove-if-not以降の条件が偽となる要素を取り除く
      ;;pivotよりも小さいものをquicksort()に投げる
             (remove-if-not #'(lambda (x) (= x pivot)) list)
             ;;pivot自身
             (quicksort (remove-if-not #'(lambda (x) (> x pivot)) list)))
             ;;pivotよりもでかいものquicksort()に投げる
      list))

Common Lispのコード久々に眺めた。
基本的な関数も忘れてた。
Common Lispの参考文献：M.Hiroi's Home Page / xyzzy Lisp Programming
けど、構造的にはPythonと同じで、less+pivot+moreを再帰的に行ってる。

感想

今回は3つの言語を比べてみた。
Cは明確に入れ替えるポイントがあるけれど、確定した領域が何となくふわっとしていてわかりにくい。
PythonとCommon Lispは入れ替えって作業自体はわざわざしてないから、納得しやすかった。
（Common Lispはいきなり読んでもわからないけど、Pythonのおかげでわかった気がする）
ただ、直感的に入れ替えをしない場合、ループする部分で計算回数って多くなりそう？みたいなことを思ったけど、確かめる気にはならなかった。。。