【AOJ ALDS1_6】B : Sort II - Partition

問題

パーティション | アルゴリズムとデータ構造 | Aizu Online Judge

方針

• iをA[r]以下の数が格納されている終端を示す変数とする.
• jをpからr-1まで進めていき, A[j]がxより大きければそのまま, x以下の場合はiを1つ進めてスワップする.
• 最後にi+1とr番目の要素をスワップし, i+1を返す.

コード

#include <bits/stdc++.h>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

int A[100001];

int partition(int p, int r){
  int i;
  i = p-1;

  REP(j, p, r){
    if(A[j] <= A[r]){
      i++;
      swap(A[i], A[j]);
    }
  }
  swap(A[i+1], A[r]);
  
  return i+1;
}


signed main(){
  int n;
  cin >> n;
  rep(i, n){
    cin >> A[i];
  }

  int ret = partition(0, n-1);
  
  rep(i, n){    
    if(i > 0) cout << " ";
    if(ret == i){
      cout << "[" << A[i] << "]";
    }else{
      cout << A[i];
    }
  }
  puts("");
}

先週末出かけてて何もできなかったので今週は頑張ろう.