K&Rを読もう(45) 4.10 & 演習4-14 クイックソートとswap

gcc

演習4-14でswapマクロを書け。という問題が出てきたので、swapマクロを使ってK&R式クイックソートを書いてみます。

K&R式クイックソート解読

クイックソートは起点となる値と比べて、起点より低い、高いでソートしていく感じ。

6 5 4 3 2 1について考えます。

  • まず中心を出します。leftが0,rightが5。(0+5)/2で、2.5になるので、切捨てて2
  • v[2]は4なので、ちょっと外に置いておきましょう。残りは6 5 3 2 1
  • 4と比べて少ないものを前に出していきます。3 2 1 6 5
  • で、ちょっと置いておいた、4を中心に戻します。1 3 2 4 6 5
  • 後は1 3 2と、6 5について再帰的にqsortするだけ。

コーディング

#include <stdio.h>
#include <stdlib.h>

#define swap(type, a, b) do {type t; t = a; a = b; b = t;} while(0)

void disp(int v[], int length)
{
    int i;

    for (i = 0; i < length; i++)
        printf("%d ", v[i]);
    printf("\n");
}

void my_qsort(int v[], int left, int right)
{
    int i, last;

    if (left >= right)
        return;
    swap(int, v[left], v[(left + right) / 2]);
    last = left;
    for (i = left + 1; i <= right; i++) {
        if (v[i] < v[left]) {
            last++;
            swap(int, v[last], v[i]);
        }
    }
    swap(int, v[left], v[last]);
    my_qsort(v, left, last - 1);
    my_qsort(v, last + 1, right);
}

int main(void)
{
    int v[] = {6, 5, 4, 3, 2, 1};

    disp(v,6);
    my_qsort(v, 0, 5);
    disp(v,6);

    return EXIT_SUCCESS;
}

実行するとこんな感じ。

6 5 4 3 2 1
1 2 3 4 5 6

Schemeで

ついでにSchemeでクイックソート

(define (qsort f l)
  (define (q-filter x l)
    (if (null? l)
        '(())
        (let* ((res (q-filter x (cdr l)))
               (left (car res))
               (right (cdr res)))
          (if (f (car l) x)
              (cons (cons (car l) left)
                    right)
              (cons left
                    (cons (car l) right))))))
  (if (null? l)
      '()
      (let* ((res (q-filter (car l) (cdr l)))
             (left (car res))
             (right (cdr res)))
        (append
          (qsort f left)
          (cons (car l) (qsort f right))))))

(qsort < '(3 2 1 5 4))
; (1 2 3 4 5)

Schemeだと中心を出すのが面倒なので、リストの先頭を起点とします。

  • (2 1 5 4)に3でq-filterをかけて、((1 2) 5 4)というように分解。
  • car,cdrに対して再帰的にqsortしてappendしていく感じ。

まとめ

「C言語によるはじめてのアルゴリズム入門」にもうちょっと高度な軸の取り方をしたクイックソートが載ってる。

色々なソート方法があるので、qsort以外も試してみたいな。

追記

appendは速度を台無しにしてる。書き直したい。