■

ここ数年、Cでクイックソートを書いていないことに気がついたので、思い出しつつ書いてみることに。

#include <stdio.h>

#define SWAP(a, b) { \
  int tmp; \
  tmp = a; a = b; b = tmp; \
}

static int avg(int elms[], int left, int right)
{
  int i, sum = 0;

  for (i = left; i <= right; i++)
    sum += elms[i];

  return (sum / (right - left + 1));
}

static void print_list(int elms[], int left, int right)
{
  int i;
  for (i = left; i <= right; i++)
    printf("%d ", elms[i]);

  printf("\n");
}

static void qs(int elms[], int left, int right)
{
  int l, r;
  int pivot = avg(elms, left, right);

  for (l = left, r = right; l < r; l++, r--) {
    for (; elms[l] < pivot; l++);
    for (; elms[r] > pivot; r--);

    if (r < l) break;

    SWAP(elms[l], elms[r]);
  }

  if (left < l - 1)
    qs(elms, left, l - 1);

  if (l < right)
    qs(elms, l, right);
}

int main(void)
{
  int len;
  int elms[] = { 7, 2, 5, 9, 6, 1, 3, 8, 4 };

  len = sizeof(elms) / sizeof(elms[0]);

  qs(elms, 0, len - 1);

  print_list(elms, 0, len - 1);

  return 0;
}

う〜ん、書き方がまずいのかコードを見ても意図が伝わりにくい気がするなぁ

OCamlだと

let qs l =
  let rec part pivot left right = function
    | [] -> (left, right)
    | hd :: tl when hd < pivot ->
        part pivot (hd :: left) right tl
    | hd :: tl ->
        part pivot left (hd :: right) tl
  in
  let rec sort = function
    | [] -> []
    | hd :: tl ->
        let left, right = part hd [] [] tl in
        sort left @ hd :: sort right
  in
  sort l

let _ =
  let elms = [7; 2; 5; 9; 6; 1; 3; 8; 4] in
  List.iter
    (fun x -> Printf.printf "%d " x) (qs elms);
  print_newline ()

と末尾再帰になっていないが、こちらのほうが意図がわかりやすくて嬉しい.
使用メモリや計算量は多いけど…