0

現在、ALDS1_6_B を行っています。

解答コードは、以下のようになります。

その中で、パーティションの中で使われているint i = p-1の意味がわかりません。
なぜ、iは、p-1を行っているのでしょうか? どういう理由で、p-1を定義しているのでしょうか?

また xを閾値として、for文の中で比較して、x未満とx以上を分けていると思うのですが、
なぜiを使うことで、大小のグループ分けができるでしょうか?
是非ご教授よろしくお願いいたします。

解答コード:

#include <stdio.h>
#include <algorithm>

using namespace std;

int partition(int A[],int p,int r){
    int x = A[r];
    int i = p-1;
    for(int j = p; j < r; j++){
        if(A[j] <= x){
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return i+1;
}

int main(){
    int n,partition_point;
    scanf("%d",&n);
    int A[n];
    for(int i = 0; i < n; i++) scanf("%d",&A[i]);

    partition_point = partition(A,0,n-1);

    for(int i = 0; i < n-1; i++){
        if(i == partition_point){
            printf("[%d] ",A[i]);
        }else{
            printf("%d ",A[i]);
        }
    }
    if(partition_point == n-1){
        printf("[%d]\n",A[n-1]);
    }else{
        printf("%d\n",A[n-1]);
    }
}

1 件の回答 1

2

どこから解説したらよいものやら・・・ quicksort のアルゴリズムは分かっていますか?

ソートしたい配列内にある1つの要素をテキトーに選んでそれより大きいか小さいかを判別するわけですが、その要素をピボットと呼びます。ピボットより小さい要素を左側に、ピボットより大きい要素を右側に集めたら、ピボット要素はその中央に置けばよいわけです。これを分割区間を変えて再帰的に繰り返すと全要素をソートできます。

以上を踏まえて

  • 例示の partition() は 配列 A の要素 A[p]A[r] を quicksort 的入れ替えを行う処理です
  • この例では int x = A[r]; がピボット、つまり最終要素をピボットとしています
  • for 内部の swap(A[i],A[j]); はピボットより小さい要素を左側に集める処理
  • 実際には「集める」のではなく「交換」することでピボットより大きい要素を右側に集める処理も兼ねている
  • for 外の swap(A[i+1],A[r]); は「ピボットを中央に置く」処理

です。

i はピボットより小さい要素の次回挿入(=交換)位置ですな。 i を基準に値を分けているわけではないっス。実際に挿入する直前に +1 しているので初期値としては p-1 と書く必要が生じて、ソースコードの記述が直観的でないかもしれません。

2
  • 774RR様 ご回答ありがとうございます。クイックソートのアルゴリズムは、理解しているのですが、なぜiが最初から-1するのかが分かりませんでしたが、次回の値を入れるための準備として、引いていると理解しました。一つ疑問があるのですが、なぜ最初から-1なのでしょうか? 自分の考え的には、iを最初からインデックスを使った値として利用して、もしswapしたらその後に+1すれば良いと思います。日常的に私が見ているプログラムでは、何かを処理した後に+1をすれば良いものを見ているのでこのように最初から-1をしていることに対して違和感を感じます。(while文とかでは、何かの処理の末尾に+1をしているのをよく見ます)。そもそもなぜ次の準備のために最初から-1して実際の処理では+1しているのでしょうか? 是非ご教授よろしくお願い致します。 2022年12月2日 14:14
  • 1
    なぜ、となるとそのコードを書いた人の設計意図となってしまうので第三者にはわかりません。オイラが同等のコードを書くとしたらあなたと同様に交換してから +1 するコードを書くでしょう。実際それで問題なく動きますし。そういう意味では閉区間 [p, r] を渡すってのも c っぽくない設計ですよね。 C に染まっちゃった人は(オイラなど)半開区間 [p, r) を渡したくなります。その辺の意図を知りたかったら出題者に直接訊くしかなさそうです。
    – 774RR
    2022年12月4日 23:06

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。