アルゴ式（beta版）の「ソートアルゴリズム」ソートアルゴリズムからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
Q2-1. バブルソート
/* C++による「ソートアルゴリズム」ソートアルゴリズムの解答例 Q2-1. バブルソート https://algo-method.com/tasks/439 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; void out(int a[],int n){ for(int i=0;i<n;i++){ cout<<a[i]<<((i==n-1) ? "\n" : " "); } } void BS(int a[],int n){ bool tf=true; while(tf){ tf=false; for(int i=0;i<n-1;i++){ if(a[i]>a[i+1]){ using std::swap; swap(a[i],a[i+1]); tf=true; } } if(tf){ out(a,n); } } } int main(void){ int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } BS(a,n); return 0; }
・Q2-2. 選択ソート
/* C++による「ソートアルゴリズム」ソートアルゴリズムの種類の解答例 Q2-2. 選択ソート https://algo-method.com/tasks/440 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; void out(int a[],int n){ for(int i=0;i<n;i++){ cout<<a[i]<<((i==n-1) ? "\n" : " "); } } void SSM(int a[],int n){//単純選択法 ->Simple Selection Method for(int i=0;i<n-1;i++){ int min1=10000; int min2=10000; int swap_number=-1; for(int j=i;j<n;j++){ min1=min(min1,a[j]); if(min1!=min2){ swap_number=j; } min2=min1; } using std::swap; swap(a[i],a[swap_number]); out(a,n); } } int main(void){ int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } SSM(a,n); return 0; }
・Q2-3. 挿入ソート
/* C++による「ソートアルゴリズム」ソートアルゴリズムの種類の解答例 Q2-3. 挿入ソート https://algo-method.com/tasks/441 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; void out(int a[],int n){ for(int i=0;i<n;i++){ cout<<a[i]<<((i==n-1) ? "\n" : " "); } } void IS(int a[],int n){ for(int i=1;i<n;i++){ int pos=i; while(pos!=0 && a[pos-1]>a[pos]){ using std::swap; swap(a[pos-1],a[pos]); pos--; } out(a,n); } } int main(void){ int n; cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } IS(a,n); return 0; }
・Q2-4. クイックソート
/* C++による「ソートアルゴリズム」ソートアルゴリズムの種類の解答例 Q2-4. クイックソート https://algo-method.com/tasks/442 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; 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++; } } 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]<<((i==n-1) ? "\n" : " "); } return 0; }
・Q2-5. 乱択クイックソート
/* C++による「ソートアルゴリズム」ソートアルゴリズムの種類の解答例 Q2-5. 乱択クイックソート https://algo-method.com/tasks/443 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; void out(vector<int> a,int n){ for(int i=0;i<n;i++){ cout<<a[i]<<((i==n-1) ? "\n" : " "); } } vector<int> RQS(vector<int> a){ int n=(int)a.size(); if(n<2){ return a; } vector<int> l,r; int ra=rand()%n; for(int i=0;i<n;i++){ if(i==ra){ continue; } if(a[i]<a[ra]){ l.push_back(a[i]); }else if(a[i]>a[ra]){ r.push_back(a[i]); }else{ int r2=rand(); if(r2%2==1){ l.push_back(a[i]); }else{ r.push_back(a[i]); } } } l=RQS(l); r=RQS(r); l.push_back(a[ra]); for(auto i : r){ l.push_back(i); } return l; } int main(void){ int n; cin>>n; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } a=RQS(a); out(a,n); return 0; }
・Q2-6. マージソート
/* C++による「ソートアルゴリズム」ソートアルゴリズムの種類の解答例 Q2-6. マージソート https://algo-method.com/tasks/444 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; void out(vector<int> a,int n){ for(int i=0;i<n;i++){ cout<<a[i]<<((i==n-1) ? "\n" : " "); } } vector<int> MS(vector<int> a){ int n=(int)a.size(); int x=n/2; vector<int> l,r; for(int i=0;i<x;i++){ l.push_back(a[i]); } for(int i=x;i<n;i++){ r.push_back(a[i]); } if(l.size()>1){l=MS(l);} if(r.size()>1){r=MS(r);} reverse(r.begin(),r.end()); for(auto i : r){ l.push_back(i); } deque<int> dl(l.begin(),l.end()); vector<int> b; while(!(dl.empty())){ int ef=dl.front(),el=dl.back(); if(ef<=el){ b.push_back(ef); dl.pop_front(); }else{ b.push_back(el); dl.pop_back(); } } return b; } int main(void){ int n; cin>>n; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } a=MS(a); out(a,n); return 0; }
・Q2-7. ヒープソートの準備
/* C++による「ソートアルゴリズム」ソートアルゴリズムの種類の解答例 Q2-7. ヒープソートの準備 https://algo-method.com/tasks/518 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; void basic_HS(vector<int> a){ int n=(int)a.size(); int x=n/2-1; while(x>=0){ int k=x; while(1){ int mn=k; if(2*k+1<n && a[mn]<a[2*k+1]){ mn=2*k+1; } if(2*k+2<n && a[mn]<a[2*k+2]){ mn=2*k+2; } if(mn==k){ break; } swap(a[k],a[mn]); k=mn; } x--; } for(int i=0;i<n;i++){ cout<<a[i]<<((i==n-1) ? "\n" : " "); } } int main(void){ int n; cin>>n; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } basic_HS(a); return 0; }
・Q2-8. ヒープソート
/* C++による「ソートアルゴリズム」ソートアルゴリズムの種類の解答例 Q2-8. ヒープソート https://algo-method.com/tasks/524 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; void little_basic_HS(vector<int> &a,int x,int n){ int k=x; while(1){ int i=2*k+1; if(i>=n){ break; } if(i!=n-1){ if(a[i+1]>a[i]){ i++; } } if(a[k]>=a[i]){ break; } swap(a[k],a[i]); k=i; } } int main(void){ int n,m; cin>>n>>m; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } int x=(n-1)/2; while(x>=0){ little_basic_HS(a,x,n); x--; } for(int i=n-1;i>=0;i--){ swap(a[0],a[i]); little_basic_HS(a,0,i); if(i==m){ for(int j=0;j<n;j++){ cout<<a[j]<<((j==n-1) ? "\n" : " "); } } } for(int i=0;i<n;i++){ cout<<a[i]<<((i==n-1) ? "\n" : " "); } return 0; }
・Q2-9. バケットソート
/* C++による「ソートアルゴリズム」ソートアルゴリズムの種類の解答例 Q2-9. バケットソート https://algo-method.com/tasks/447 提出コードの解答例 https://neguse-atama.hatenablog.com */ //今回は関数なし #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<int> a(n),num(n+1,0),sum(n+1),b(n); for(int i=0;i<n;i++){ cin>>a[i]; num[a[i]]++; } sum[0]=num[0]; for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+num[i]; } for(int i=0;i<n;i++){ sum[a[i]]--; b[sum[a[i]]]=a[i]; } for(int i=0;i<n;i++){ cout<<b[i]<<((i==n-1) ? "\n" : " "); } return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
