クイックソートのソースコードについて

Question

クイックソートのプログラムなのですが、

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

/*--- クイックソート ---*/
void quick(int a[], int left, int right)
{
	int pl = left;				/* 左カーソル */
	int pr = right;				/* 右カーソル */
	int x = a[(pl + pr) / 2];	/* 枢軸は中央の要素 */

	do {
		while (a[pl] < x) pl++;
		while (a[pr] > x) pr--;
		if (pl <= pr) {
			swap(int, a[pl], a[pr]);
			pl++;
			pr--;
		}
	} while (pl <= pr);

	if (left < pr)  quick(a, left, pr);
	if (pl < right) quick(a, pl, right);
}

を

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

/*--- クイックソート ---*/
void quick(int a[], int left, int right)
{
	int pl = left;				/* 左カーソル */
	int pr = right;				/* 右カーソル */
	int x = a[(pl + pr) / 2];	/* 枢軸は中央の要素 */

	while (pl <= pr)
         {
		while (a[pl] < x) pl++;
		while (a[pr] > x) pr--;
		if (pl <= pr) {
			swap(int, a[pl], a[pr]);
			pl++;
			pr--;
        };
	if (left < pr)  quick(a, left, pr);
	if (pl < right) quick(a, pl, right);
}

に変更しても処理結果は変わるでしょうか？
do-whileをwhileに変更しています。
do-whileとwhileの処理の違いはわかるのですが、それで実際にソートに差が出るのかわかりません。

Answer 1

変わるのは left > right の時ですが、それが起こり得るのは最初の一回だけです。再起呼び出しではその条件は除外してあるので、最初の一回さえ気をつければ変わりません。

Comments

[Zuishin]

ちなみに left > right で呼び出すと do の方はまずいことになります。

Answer 2

do-whileとwhileの処理の違いはわかるのですが、それで実際にソートに差が出るのかわかりません。

• do-while: left > rightのときでも実行する。インデックスが範囲外に出ることがある。
• while: left > rightのとき実行しない。ソートしない。

インデックスが範囲外に出る可能性があるのは、以下の文です。

        while (a[pl] < x) pl++;
        while (a[pr] > x) pr--;

left > rightのとき、do-whileは不具合を起こすことがありますが、whileは不具合を起こさないので防禦的なコードだといえます。だからといって優劣が決まるわけではない。ソートの仕様が提示されていないからです。たとえば次のような仕様が考えられます。

• 事前条件 配列の要素数は2以上、left <= right であること、0 <= left,right < 要素数
• 事後条件 配列の要素が昇順にならんでいること。
• 不変条件 配列の要素が欠けたり追加されないこと。

クイックソートの呼び出し側は事前条件を守るべきで、left > rightで呼び出すなら、結果は保証されない。つまり、仕様次第では、do-whileに欠陥があるといえません。

ちょうど今、「契約による設計」を勉強しているので、思ったことを書いてみました。

Answer 3

ちょっと見＆インデントが分かりづらいので修正・・・

#define swap(type, x, y)                                                       \
    do {                                                                       \
        type t = x;                                                            \
        x      = y;                                                            \
        y      = t;                                                            \
    } while (0)

/*--- クイックソート ---*/
void quick(int a[], int left, int right)
{
    int pl = left;             /* 左カーソル */
    int pr = right;            /* 右カーソル */
    int x  = a[(pl + pr) / 2]; /* 枢軸は中央の要素 */

    while (pl <= pr) {
        while (a[pl] < x)
            pl++;
        while (a[pr] > x)
            pr--;
        if (pl <= pr) {
            swap(int, a[pl], a[pr]);
            pl++;
            pr--;
        };
        if (left < pr)
            quick(a, left, pr);
        if (pl < right)
            quick(a, pl, right);
    }

変わるとしたらpl == prの時ですかね？
・・・do{…}while;の方はそれでも動いちゃいますが？

Comments

[退会済みユーザー]

どちらの処理でもソート内容自体に変わりはありますか？

[cateye]

余談：千〜２千ぐらいならシェルソートを使いましょう（シェル大好きｗ）・・・どっちにしても安定なソートではないｄ＾＾

[cateye]

実行環境を作ってプリントデバッグｄ＾＾　plとprを見てみれば？・・・追いかけるほど頭回らないσ(ﾟ∀ﾟ )

Answer 4

while は処理の前に条件判断となり、条件次第では処理が全く行われません。
do while だと、処理が終わってから条件判断となり、必ず１回は処理を行うことになるってことで、そこの違いになりますんで、そこらへんで処理が変わるかですね

Comments

[退会済みユーザー]

どちらの処理でもソート内容自体に変わりはありますか？

Answer 5

原理上は起こり得ないが（そもそも初期でleft>rightの場合は値渡しがおかしいので）、万が一ミスった際の対策でdo-whileになっていると解釈しました。
皆様のおかげで理解しました、ありがとうございました。

Answer 6

どんな差が出るかを、
ソート結果、 sawp が実行される回数、quick メソッドが呼びし回数
で比べてみました。

x.c

#include <stdio.h>

#define swap(type, x, y) do { type t = x; x = y; y = t; swap_count++;} while (0)

int swap_count;
int call_count;

/*--- クイックソート ---*/
void quickA(int a[], int left, int right)
{
  int pl = left;               /* 左カーソル */
  int pr = right;              /* 右カーソル */
  int x = a[(pl + pr) / 2];    /* 枢軸は中央の要素 */

  call_count++;
  do {
    while (a[pl] < x) pl++;
    while (a[pr] > x) pr--;
    if (pl <= pr) {
      swap(int, a[pl], a[pr]);
      pl++;
      pr--;
    }
  } while (pl <= pr);

  if (left < pr)  quickA(a, left, pr);
  if (pl < right) quickA(a, pl, right);
}

void quickB(int a[], int left, int right)
{
  int pl = left;               /* 左カーソル */
  int pr = right;              /* 右カーソル */
  int x = a[(pl + pr) / 2];    /* 枢軸は中央の要素 */

  call_count++;
  while (pl <= pr) {
    while (a[pl] < x) pl++;
    while (a[pr] > x) pr--;
    if (pl <= pr) {
      swap(int, a[pl], a[pr]);
      pl++;
      pr--;
    };
    if (left < pr)  quickB(a, left, pr);
    if (pl < right) quickB(a, pl, right);
  }
}

void copy_to_a(int src[], int a[], int size) {
  for (int i = 0; i < size; i++) {
    a[i] = src[i];
  }
}

void show_a(int a[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", a[i]);
  }
  printf(" swap_count(%d), call_count(%d)\n", swap_count, call_count);
}

int main(void) {

  int test [][3] = {
    {1, 2, 3},
    {1, 3, 2},
    {2, 1, 3},
    {2, 3, 1},
    {3, 1, 2},
    {3, 2, 1}
  };

  for (int i = 0; i < 6; i++) {
    int a[3];

    printf("----------\n");
    swap_count = call_count = 0;
    show_a(test[i], 3);

    copy_to_a(test[i], a, 3);
    swap_count = call_count = 0;
    quickA(a, 0, 2);
    show_a(a, 3);

    copy_to_a(test[i], a, 3);
    swap_count = call_count = 0;
    quickB(a, 0, 2);
    show_a(a, 3);
  }
  return 0;
}

実行例

[3, 2, 1] をソートしたときに、ソート結果は同じですが、メソッドの呼び出し回数、swap の実行回数に差異があります。

３要素の配列でためしていますが、ご自身で、もっと要素数が多いときに常にソート結果は同じなのか、計算量の差はどのくらい異なるのかなどを調べてみることをお勧めします。

[100, 99, ... 1] の配列をソートして比較すると、きっと驚くだろうと予想してます。(私は驚きました)
もし実際に比較してみていただけたなら結果をコメントにでも書いてもらえれば幸いです。

追記
上のコードの quickB は質問文のものと違ってました。
修正したコードと実行結果を示します。

#include <stdio.h>

#define swap(type, x, y) do { type t = x; x = y; y = t; swap_count++;} while (0)

int swap_count;
int call_count;

/*--- クイックソート ---*/
void quickA(int a[], int left, int right)
{
  int pl = left;               /* 左カーソル */
  int pr = right;              /* 右カーソル */
  int x = a[(pl + pr) / 2];    /* 枢軸は中央の要素 */

  call_count++;
  do {
    while (a[pl] < x) pl++;
    while (a[pr] > x) pr--;
    if (pl <= pr) {
      swap(int, a[pl], a[pr]);
      pl++;
      pr--;
    }
  } while (pl <= pr);

  if (left < pr)  quickA(a, left, pr);
  if (pl < right) quickA(a, pl, right);
}

void quickB(int a[], int left, int right)
{
  int pl = left;               /* 左カーソル */
  int pr = right;              /* 右カーソル */
  int x = a[(pl + pr) / 2];    /* 枢軸は中央の要素 */

  call_count++;
  while (pl <= pr) {
    while (a[pl] < x) pl++;
    while (a[pr] > x) pr--;
    if (pl <= pr) {
      swap(int, a[pl], a[pr]);
      pl++;
      pr--;
    };
  }
  if (left < pr)  quickB(a, left, pr);
  if (pl < right) quickB(a, pl, right);
}

void copy_to_a(int src[], int a[], int size) {
  for (int i = 0; i < size; i++) {
    a[i] = src[i];
  }
}

void show_a(int a[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", a[i]);
  }
  printf(" swap_count(%d), call_count(%d)\n", swap_count, call_count);
}

int main(void) {

  int test [][3] = {
    {1, 2, 3},
    {1, 3, 2},
    {2, 1, 3},
    {2, 3, 1},
    {3, 1, 2},
    {3, 2, 1}
  };

  for (int i = 0; i < 6; i++) {
    int a[3];

    printf("----------\n");
    swap_count = call_count = 0;
    show_a(test[i], 3);

    copy_to_a(test[i], a, 3);
    swap_count = call_count = 0;
    quickA(a, 0, 2);
    show_a(a, 3);

    copy_to_a(test[i], a, 3);
    swap_count = call_count = 0;
    quickB(a, 0, 2);
    show_a(a, 3);
  }

  int aa[100];
  for (int i = 0; i < 100; i++) {
    aa[i] = 100 - i;
  }
  swap_count = call_count = 0;
  quickB(aa, 0, 99);
  show_a(aa, 100);

  for (int i = 0; i < 100; i++) {
    aa[i] = 100 - i;
  }
  swap_count = call_count = 0;
  quickA(aa, 0, 99);
  show_a(aa, 100);


  return 0;
}

実行例

Comments

[Bull]

quickB の '}' の位置が quickA とは違います。
それを直すと呼び出し回数と、swap の回数は同じになります。

[katoy]

あ、間違えた！
コードを paste して来て { } を追加編集したのですが、そこで間違えてました。
修正したコードと実行結果を追記します。