paizaラーニングのレベルアップ問題集「効率的なソートアルゴリズムメニュー」からの出典です。
paiza.jp
C++による「効率的なソートアルゴリズムメニュー」問題集と、それらの提出コードの解答例です。
僕が作成、提出したコードは、以下のとおりです。
/* C++による「効率的なソートアルゴリズムメニュー」問題集 FINAL問題 シェルソート https://paiza.jp/works/mondai 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; void insertion_sort(int a[],int n,int h){ int cnt=0,x,j; for(int i=h;i<n;i++){ x=a[i]; j=i-h; while((j>=0) && (a[j]>x)){ a[j+h]=a[j]; j-=h; cnt++; } a[j+h]=x; } cout<<cnt<<endl; } void shell_sort(int a[],int n,vector<int> h){ for(int i=0;i<h.size();i++){ insertion_sort(a,n,h[i]); } } int main(void){ int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } int k; cin>>k; vector<int> h(k); for(int i=0;i<k;i++){ cin>>h[i]; } shell_sort(a,n,h); return 0; }
/* C++による「効率的なソートアルゴリズムメニュー」問題集 FINAL問題 マージソート https://paiza.jp/works/mondai 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; #define INF 1000000001 int cnt=0; void merge(int a[],int left,int mid,int right){ int nl=mid-left+1; int nr=right-mid+1; int l[nl],r[nr]; for(int i=0;i<nl-1;i++){ l[i]=a[left+i]; } for(int i=0;i<nr-1;i++){ r[i]=a[mid+i]; } l[nl-1]=INF; r[nr-1]=INF; int lindex=0; int rindex=0; for(int i=left;i<right;i++){ if(l[lindex]<r[rindex]){ a[i]=l[lindex]; lindex++; }else{ a[i]=r[rindex]; rindex++; cnt++; } } } void merge_sort(int a[],int left,int right){ if((left+1)<right){ int mid=(left+right)/2; merge_sort(a,left,mid); merge_sort(a,mid,right); merge(a,left,mid,right); } } int main(void){ int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } merge_sort(a,0,n); for(int i=0;i<n;i++){ cout<<a[i]; if(i!=n-1){ cout<<" "; }else{ cout<<endl; } } cout<<cnt<<endl; return 0; }
/* C++による「効率的なソートアルゴリズムメニュー」問題集 FINAL問題 クイックソート https://paiza.jp/works/mondai 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int cnt=0; void quick_sort(int a[],int left,int right){ if(left+1>=right){ return; } int pivot=a[right-1]; int cur_index=left; for(int i=left;i<right-1;i++){ if(a[i]<pivot){ using std::swap; swap(a[cur_index],a[i]); cur_index++; cnt++; } } swap(a[cur_index],a[right-1]); quick_sort(a,left,cur_index); quick_sort(a,cur_index+1,right); } int main(void){ int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } quick_sort(a,0,n); for(int i=0;i<n;i++){ cout<<a[i]; if(i!=n-1){ cout<<" "; }else{ cout<<endl; } } cout<<cnt<<endl; return 0; }
paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。