12/17 : 整列 (sorting)

N 個のデータが配列 A に入っているとする. これを大きい順に並べ換える方法として次のものが考えられる.

1. 最大のものを A[0] へ, A[1] 以降で最大のものを A[1] へ $\ldots$

   
   for ( I = 0; I < N; I++ )
       for ( J = I+1; J < N; J++ )
           if ( A[I] < A[J] )
               swap(A,I,J);
   

   ここで, swap(A,I,J) は配列 A の第 I, J 要素 を入れ換える関数である.

   
   def swap(A,I,J) {
       T = A[I]; A[I] = A[J]; A[J] = T;
   }
   

2. 一つ前より大きいものを前に送る操作を後ろから前に向かって行う (バブルソート).

   
   for ( I = 0; I < N; I++ )
       for ( J = N-1; J > I; J-- )   /* A[I] が終点 */
           if ( A[J] > A[J-1] )
               swap(A,J,J-1);
   

3. 適当な要素 $M$ をとり A の要素を $X \le M$ と $X>M$ に 分け, それぞれに同じ操作を適用 (クイックソート).

最初の二つのアルゴリズムの計算量は $O(N^2)$ (比較が $1/2 N^2$回ある.) クイックソートでは, いつも要素が半分になれば,

$$Q(2^n) = 2^n+2Q(2^{n-1})=2^n+2^n+2^2Q(2^{n-2})=\ldots = n2^n$$

より

$$Q(N) = O(N \log_2 N)$$

よって, クイックソートの理想的計算量は $O(N \log_2 N)$. しかし 最悪は $O(N^2)$ である.

問 17.1   クイックソートの最悪計算量を与える入力はどのようなものか.

クイックソートは再帰で書くと自然に書ける.

/* sort A[B]...A[E] in increasing order */

def qs(A,B,E) {
    if ( B >= E ) return; /* nothing to be done */
    M = idiv(B+E,2);
    Sep = A[M];  /* Sep : separator */
    swap(A,B,M); /* put the separator at the top of A */
    Last = B;
    /* A[B+1],...,A[Last] < Sep, A[Last+1],...,A[I-1] >= Sep */
    for ( I = B+1; I <= E; I++ )
        if ( A[I] < Sep ) {
            Last++;
            swap(A,I,Last);
        }
    /*restore the separator */
    swap(A,B,Last);
   /* recursion for the two parts */
    qs(A,B,Last-1);
    qs(A,Last+1,E);
}

注意 17.1   配列の中の移動のみで, 元の配列を Sep 未満, および Sep 以上 の元に分けるのに, Last という変数がうまく使われていることを 理解, 鑑賞すること. このプログラムは C 言語の教科書「プログラミング言語 C」(カーニハン, リッチー) からとった.

再帰のたびに余分なメモリが必要になるが, リストを用いた次のような 分かりやすいプログラムも書ける.

def qs_list(L)
{
    if ( L == [] )
        return L;
    /* use the first element of L as a separator */
    /* it is somewhat dangerous (why?) */
    Sep = car(L);
    L = cdr(L);
    /* Left will be the set of elements less than or equal to Sep */
    /* Right will be the set of elements greater than Sep */
    Left = [];
    Right = [];
    for ( ; L != []; L = cdr(L) ) {
        T = car(L);
        if ( T <= Sep )
            Left = cons(T,Left);
        else
            Right = cons(T,Right);
    }
    /* recursion */
    Left = qs_list(Left);
    Right = qs_list(Right);
    /* Left + [Sep] + Right => sorted list */
    return append(Left,cons(Sep,Right));
}

問 17.2   どの部分で余分にメモリを使っているか.

演習 17.1   配列, リスト版それぞれのプログラムを実際に動作させてみて, 計算速度を比較せよ.