anonymous quickSort
No License C++
2019年06月21日
Copy Clone
#include<iostream>
#include<vector>

int partion(std::vector<int>&A,int left,int right){
  int x=A[right];
  int i=left-1;
  for(int j=left;j<right;++j){
    if(A[j]<=x){
      i++;
      std::swap(A[i],A[j]);
    }
  }
  std::swap(A[i+1],A[right]);
  return i+1;
}

void quickSort(std::vector<int>&A,int left,int right){
  if(left<right){
    int q=partion(A,left,right);
    quickSort(A,left,q-1);
    quickSort(A,q+1,right);
  }
}

int main(){

  int n;
  std::cin>>n;
  std::vector<int> A(n);
  for(int i=0;i<n;++i)std::cin>>A[i];

  quickSort(A,0,n-1);
  for(int i=0;i<n;++i)std::cout<<A[i]<<" ";
  std::cout<<std::endl;

  return 0;
}
#include<iostream>
#include<vector>

int partion(std::vector<int>&A,int left,int right){
  int x=A[right];
  int i=left-1;
  for(int j=left;j<right;++j){
    if(A[j]<=x){
      i++;
      std::swap(A[i],A[j]);
    }
  }
  std::swap(A[i+1],A[right]);
  return i+1;
}

void quickSort(std::vector<int>&A,int left,int right){
  if(left<right){
    int q=partion(A,left,right);
    quickSort(A,left,q-1);
    quickSort(A,q+1,right);
  }
}

int main(){

  int n;
  std::cin>>n;
  std::vector<int> A(n);
  for(int i=0;i<n;++i)std::cin>>A[i];

  quickSort(A,0,n-1);
  for(int i=0;i<n;++i)std::cout<<A[i]<<" ";
  std::cout<<std::endl;

  return 0;
}
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
P.158~167
No one still commented. Please first comment.