クイックソートを書いていてハマった話

今日はクイックソートでハマったことを書きたいと思います。クイックソートはデータを小さい順（または大きい順）に並べるアルゴリズムです。ここでは与えられたデータを「集合」と呼びますが、数学で扱う集合とは異なり、同じ要素を複数含んでいても良いことにします。

クイックソートでは、データの集合Sを3つの部分に分割します。そのためにある基準となる値（ピボットと呼ばれる）xを決めます。xは集合Sの中から取ってくることにします。第一の集合は、xよりも小さい要素の集合S1です。第二は、データxと同じ値を持つ要素の集合S2。第三はxよりも大きい値を持つ要素の集合S3です。S2は同じ値の要素だけなので、すでに整列されています。次の段階は、S1とS3について同じ方法でソートすることです。これらの集合は要素の数がSより小さいので、同じアルゴリズムの有限回の繰り返しで整列が完了します。

このアルゴリズムは完全なのですが、3分割を2分割で済ませられれば、実装が簡単になります。例えば、S1は同じで、S2とS3を一つの集合S4にするのです。 つまりSがxより小さい要素の集合、S4がx以上の要素の集合になります。 ところがこれだとうまくいかない場合があるのです。xの取り方によってはSの全ての要素がx以上であることがあり得ます。その場合S1は空集合、S4はSに等しくなります。ということは、S4の要素の数が減りませんから、アルゴリズムを繰り返すと無限ループに陥ってしまいます。このバグに気づくまで、何時間もかかってしまいました(TT)。

最初の方法では、xがSの要素で、S2が空ではないことが効いています。第二の方法では何らかの方法で、無限ループを回避することが必要です。例えば、S1が空集合だった場合に、S4をS2とS3に分けることにより、第一の方法に帰着させることが考えられます。この方法で書いたCプログラムを以下に載せておきます。何か間違いがあったら、コメントで指摘していただくと助かります。

クイックソート：　配列a[]のインデックスlからhまでの要素を整列する。

void
q_sort(int a[], int l, int h) {
  int swap, l1, h1, s;

  if (l >= h)
    return;
  s = a[(l+h)/2];
  l1 = l;
  h1 = h;
  while (l1 <= h1) {
    for (;a[l1] < s; ++l1)
      ;
    for (;a[h1] >= s;--h1)
      ;
    if (l1 < h1) {
      swap = a[l1];
      a[l1++] = a[h1];
      a[h1--] = swap;
    }
  }
  if (l1 == l) {
    h1 = h;
    while (l1 < h1) {
      for (;a[l1] == s; ++l1)
        ;
      for (;a[h1] > s;--h1)
        ;
      if (l1 < h1) {
        swap = a[l1];
        a[l1++] = a[h1];
        a[h1--] = swap;
      }
    }
  }
  if (h1 == h)
    return;
  q_sort (a, l, h1);
  q_sort (a, l1, h);
}

追記：

投稿後、「プログラム言語 C」のクイックソートプログラムを見たら、発想は同じだが、もっとスマートなプログラムでした。当然ですね。当時の最先端の研究者のプログラムですから。

この方法は、xがS4の最小値であることを利用するものです。はじめに、配列中のxを値に持つ要素を配列の端（プログラム言語Cでは左端）と交換して、残りの部分で集合S1と集合S4に分けます。そのあと、はじめに端に置いた要素と、S1の右端の要素（最初に左端においた場合）を交換、またはS2の左端の要素（最初に右端においた場合）と交換します。あらためて、xより小さい要素の集合をS1、最後に端から中間に移動した要素を除いたx以上の要素の集合をS2とします。

(1)   S1={s|s<x}
(2)   端から中間に移動した要素
(3)   S4={s|s>=x,ただし、端から中間に移動した要素を除く}

これで、S4がSよりも少ない要素数になり、無限ループを避けることができます。

やはり、基本は3つの部分に分けることだったんですね。「プログラム言語C」のクイックソートをそのまま載せるわけにはいかないので、新たにプログラムを書きました。このプログラムでは右端にピボット要素を移動しています。

追記の追記：

申し訳ありません。プログラムにバグがありましたので、修正しました。

• 14行目のwhile文の不等号<を<=に修正しました。
• 15行目と17行目のfor文の条件に、15行目に「&& l1<=h-1」17行目に「&& h1 >= l」を入れました。

static void
q_sort(int a[], int l, int h) {
  int swap, l1, h1, s, mid;

  if (l >= h)
    return;
  mid = (l + h) / 2;
  s = a[mid];
  swap = a[h];
  a[h] = a[mid];
  a[mid] = swap;
  l1 = l;
  h1 = h-1;
  while (l1 <= h1) {
    for (;a[l1] < s && l1<=h-1; ++l1)
      ;
    for (;a[h1] >= s && h1 >= l;--h1)
      ;
    if (l1 < h1) {
      swap = a[l1];
      a[l1++] = a[h1];
      a[h1--] = swap;
    }
  }
  swap = a[h];
  a[h] = a[l1];
  a[l1++] = swap;
  q_sort (a, l, h1);
  q_sort (a, l1, h);
}