92530


現在、[ALDS1_6_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_B)
を行っています。

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

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

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

**解答コード:**

[code]

    #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]);
        }
    }
    
[/code]


CC BY-SA 4.0
2022-12-01T10:41:01.297
92525
2022-12-02T01:20:13.863
2022-12-02T00:06:05.543
3060
47147
question
アルゴリズム データ構造
クイックソートのパーティションの定義について


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

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

以上を踏まえて

  * 例示の `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` と書く必要が生じて、ソースコードの記述が直観的でないかもしれません。


CC BY-SA 4.0
2022-12-02T01:20:13.863
92530
2022-12-02T01:20:13.863
8589
92525
answer