寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例

アルゴ式(beta版)の「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例

僕が作成、提出したコードは、以下のとおりです。

Q5-1. バブルソート

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-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;
}
・Q5-2. 選択ソート

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-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;
}
・Q5-3. 挿入ソート

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-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;
}
・Q5-4. クイックソート

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-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;
}
・Q5-5. 乱択クイックソート

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-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;
}
・Q5-6. マージソート

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-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;
}
・Q5-7. ヒープソートの準備

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-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;
}
・Q5-8. ヒープソート

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-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;
}
・Q5-9. バケットソート

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」ソートアルゴリズムの解答例
Q5-9. バケットソート
https://algo-method.com/tasks/524
提出コードの解答例
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