質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.80%

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 3,545

KIYZ

score 17

前提・実現したいこと

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);
   }
}

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • episteme

    2018/12/26 21:08

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

    キャンセル

  • 退会済みユーザー

    退会済みユーザー

    2018/12/26 21:16

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

    キャンセル

  • 退会済みユーザー

    退会済みユーザー

    2018/12/26 23:07

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

    キャンセル

回答 2

checkベストアンサー

+1

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

疑問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]からA[len](A[i+(len-i)])までの配列に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 ★これがソート後の配列の中身

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/04 12:12

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

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

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

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

    キャンセル

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/04 12:17

    ありがとうございます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.80%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る