クイックソートの処理の流れと実装内容が理解できません。

Question

前提・実現したいこと

1.関数に渡された配列の要素をクイックソートを用いて昇順に並び替えるプログラムの処理の流れと実装内容を理解しようとしています。
再帰処理の部分の実装内容を理解して全体の流れをイメージできるようになりたい。

2.プログラムの改変

理解したいソースコード

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#C

#include <stdio.h>
 
void quicksort(int *A, int len);
 
int main (void) {
  int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
  int n = sizeof a / sizeof a[0];
 
  int i;
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
 
  quicksort(a, n);
 
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
 
  return 0;
}
 
void quicksort(int *A, int len) {
  if (len < 2) return;
 
  int pivot = A[len / 2];
 
  int i, j;
  for (i = 0, j = len - 1; ; i++, j--) {
    while (A[i] < pivot) i++;
    while (A[j] > pivot) j--;
 
    if (i >= j) break;
 
    int temp = A[i];
    A[i]     = A[j];
    A[j]     = temp;
  }
 
  quicksort(A, i); // *1
  quicksort(A + i, len - i); // *2
}

自分が理解しやすいように書き直したソースコード

#include <stdio.h>

void   swap_elms(int *array, int a, int b)
{
   int buf;

   buf = array[a];
   array[a] = array[b];
   array[b] = buf;
}

void   quicksort(int *array, int len)
{
   if (len < 2) return;

   int pivot;
   int large;
   int small;

   pivot = array[len / 2];
   large = 0;
   small = len - 1;
   while (1)
   {
      while (array[large] < pivot)
         large++;
      while (array[small] > pivot)
         small--;

      if (large >= small)
         break;

      swap_elms(array, large, small);

      large++;
      small--;
   }

   quicksort(array, large); // *1
   quicksort(array + large, len - large); // *2
}

int    main(void)
{
   int i;
   int size = 10;
   int array[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};

   for (i = 0; i < size; i++)
      printf("%d, ", array[i]);
   printf("\n");

   quicksort(array, size);

   for (i = 0; i < size; i++)
      printf("%d, ", array[i]);

   return (0);
}

疑問

1.0「*1は配列内のピボット以下の値が集まった範囲をソートするために quicksort() を呼び出している。」という解釈で正しいのか。

1.1 「*1の quicksort() に渡している第一引数は、配列内のピボット以下の範囲の先頭の要素を指し、第二引数は配列内のピボット以下の範囲の最後の要素の次の要素を指している。」という解釈で正しいのか。

2.0「*2はピボット以上の値が集まった範囲をソートするために quicksort() を呼び出している。」という解釈で正しいのか。

2.1 *2の quicksort() に渡している二つの引数はそれぞれ何を指しているのか。なぜ A + i と len - i となっているのか。(ここが一番理解できない部分ですので、初学者でも分かるように解説して頂けると幸いです。

3.0 このプログラムのピボット選択の部分を改変したいと思っています。配列の先頭、真ん中、最後の要素から中央値となる要素を選択してそれをピボットとして扱うにはどのような実装にすれば良いでしょうか。中央値を選択するための関数を作成して試行錯誤しましたが上手く実装できません。

ピボット選択時に3つの要素から中央値を選択するための関数

int    median3(int *array, int a, int b, int c)
{
   if (array[a] < array[b])
   {
      if (array[b] < array[c])
         return (b);
      else if (array[c] < array[a])
         return (a);
      return (c);
   }
   else
   {
      if (array[c] < array[b])
         return (b);
      else if (array[a] < array[c])
         return (a);
      return (c);
   }
}

よろしくお願い致します。

Comments

[退会済みユーザー]

「再帰1」というのは1回目の再帰という意味でしょうか？

[KIYZ]

いいえ、 「// 再帰1」とコメントした行のコード(quicksort(array, large);) のことです。
「再帰2」も同じで、「n回目の再帰」という意味ではありません。

説明中に一言でこの行のコードを指せるようにするためにコメントしたのですが、却って分かりづらくなってしまったようですね。申し訳ありません。

[KIYZ]

質問文とコード内のコメントを変更しました。
再帰1 => *1
再帰2 => *2

[退会済みユーザー]

あなたが書き直したソースコードはクイックソートではないです。

[退会済みユーザー]

すみません、というか元々がクイックソートじゃないです

[episteme]

え？ これがクイックソートじゃなかったら何なの?

[退会済みユーザー]

ごめんなさい、完全に自分が勘違いしていました。
下で回答します。

[退会済みユーザー]

大量に勘違い、読み間違いをしていました。
不快な思いをさせて大変申し訳ございません。
病院に行って頭を見てもらおうと思います。

Answer 1

例えばここのように、ソートの動作を可視化して説明しているサイトなんかもありますので、理解の一助になれば。

Comments

[KIYZ]

ありがとうございます。

Answer 2

勘違いして申し訳ございません。

疑問1.0)はい、そうです。
疑問1.1)はい、そうです。
疑問2.0)はい、そうです。
疑問2.1)第一引数がその配列の開始位置です。第二引数にはその配列の長さ**（開始位置に長さを足せばその配列の末尾がわかる）**を渡しています。
*1を抽象的に言うと「pivot以下の値が集まった配列をクイックソートしてください、その配列の開始位置はAでその配列の要素の数はiです」という意味です。つまり「A[0]からA[i]までの配列にpivot以下の値が格納されている、それをソートしてください」という意味です。
今、インデックス0からインデックスiまでの配列要素にpivot以下の値が集まっています。
インデックスlen-iからインデックスlenまでの配列要素にpivot以上の値が集まっています。
インデックスiからインデックスlenまでの配列要素にpivot以上の値が集まっています。
その時(pivot以上の値が格納されている配列の)開始位置はA+iで、その配列の長さはlen-iなので
quicksort(A + i, len - i); // *2 という関数の呼び方をしています。
つまり「A[i]からAlenまでの配列にpivot以上の値が格納されている、それをソートしてください」という意味です。
3.0）中央値を選ぶことはできません。中央値を選ぼうとする行為に時間がかかってしまうので。なので少ない計算量で中央値に近い値を選ぶことがポイントです。たとえば二つの値をランダムにとってその平均をpivotにするとか。
ごめんなさい、質問内容が読めてませんでした。その三つの値から中央値を選ぶことは可能です。
三つの値のとりかたはランダムに選ぶのもいいですし、質問者様がいうように先頭、真ん中、末尾の値でもいいと思います。
質問者様が実装した関数でpivotを選んでも上手く動作しました。
pivot部分を以下のように書き換えれば上手く動作すると思います

  int index;
  index = median3(A,0,len/2,len);
  int pivot = A[index];

処理の流れを理解しやすくする為にprint文を仕込んでみました。
これを実行してみてください。

#include <stdio.h>

void quicksort(int *A, int len, int deep);
void printspace(int deep);

int main (void) {
  int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1,3};
  int n = sizeof a / sizeof a[0];
  printf("%d\n", n);

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

  quicksort(a, n, 0);

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

  return 0;
}

void quicksort(int *A, int len, int deep) {

    int k;
    printspace(deep);
    printf("配列の中身：");
  for (k = 0; k < len; k++) {
    printf("%d ", A[k]);
  }
    printf("\n");



  if (len < 2){
    printspace(deep);
    printf("配列の要素数が1以下なのでソート終了 要素の値:%d 深さ：%d\n",A[0], deep);
      return;
  }

  int pivot = A[len / 2];


  int i, j;
  for (i = 0, j = len - 1; ; i++, j--) {
    while (A[i] < pivot) i++;
    while (A[j] > pivot) j--;

    if (i >= j) break;

    int temp = A[i];
    A[i]     = A[j];
    A[j]     = temp;
  }

    printspace(deep);
  printf("pivot:%d以下の配列leftをクイックソートする\n", pivot);
  quicksort(A, i, deep+1);
    printspace(deep);
  printf("pivot:%d以上の配列rightをクイックソートする\n", pivot);
  quicksort(A + i, len - i, deep+1);
    printspace(deep);
    printf("配列の中身(ソート後)：");
  for (k = 0; k < len; k++) {
    printf("%d ", A[k]);
  }
    printf("\n");


}

void printspace(int deep){
    int i;
    for(i=0;i<deep;i++){
        printf("-----");
    }
}

「-----」このprint出力で再帰の深さを示しています。
pivot:99以上の配列rightをクイックソートする
-----配列の中身：782 99 ★これがソート前の配列の中身
-----pivot:99以下の配列leftをクイックソートする
----------配列の中身：99
----------配列の要素数が1以下なのでソート終了 要素の値:99 深さ：2
-----pivot:99以上の配列rightをクイックソートする
----------配列の中身：782
----------配列の要素数が1以下なのでソート終了 要素の値:782 深さ：2
-----配列の中身(ソート後)：99 782 ★これがソート後の配列の中身

Comments

[KIYZ]

返事が遅くなってしまい申し訳ありません。

大変ご丁寧なご説明をして頂き誠にありがとうございます。
順を追って説明して頂いたお陰で疑問が解けました。

疑問3.0に関しては、 median3() がインデックスを返す関数であるにも関わらず、
pivot = median3(array, 0, len / 2, len);
としていた事が原因で問題が生じていましたが、
pivot = array[median3(array, 0, len / 2, len)];
とすることで問題なく動作しました。

また、ここまで処理の流れや再帰深度を分かりやすく可視化できるprintf()デバッグは行ったことが無かったので、そちらも大変勉強になりました。今後活用させて頂きます。