AIZU ONLINE JUDGE 2初等的ソート

関数の仮引数、実引数

2_A(バブルソート)

#include <bits/stdc++.h>
using namespace std;

int bubbleSort(int A[],int N){
    int cnt=0;
    for (int i=0; i<N-1; i++){
        for (int k=N-1; k>i; k--){
            if (A[k]<A[k-1]){
                swap(A[k],A[k-1]);
                cnt++;
            } 
        }
    }
    return cnt;
}

int main(){
    int N; cin >> N;
    int A[101];
    for (int i=0; i<N; i++) cin >> A[i];
    int ans=0;

    ans=bubbleSort(A,N);

    for (int i=0; i<N-1; i++) cout << A[i] << " ";
    cout << A[N-1] << endl;
    cout << ans << endl;

    return 0;
}

2_B(選択ソート)

#include <bits/stdc++.h>
#define rep(i,n) for (ll i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int Selection_Sort(int A[], int N){
    int cnt=0;
    for (int i=0; i<N-1; i++){
        int min=A[i];//先頭の値を暫定の最小値として初期化する
        int k=i;//先頭の位置を保存する
        for (int j=i+1; j<N; j++){
            //
            if(min>A[j]){
                min=A[j];
                k=j;
            }
        }
        //交換するアルゴリズム
        if(A[i]!=A[k]){
            swap(A[i],A[k]);
            cnt++;
        }
    }
    return cnt;
}

int main(){
    int N; cin >> N;
    int A[101];
    int ans;
    rep(i,N) cin >> A[i];
    ans=Selection_Sort(A,N);
    rep(i,N-1) cout << A[i] << " ";
    cout << A[N-1] << endl;

    cout << ans << endl;
}

2_C(安定なソート)

#include <bits/stdc++.h>
using namespace std;

struct Card{
    char suit,value;//suit=S,H,C,Dのアルファベット value=1~9の数値
};

void bubble(Card A[],int N){
    for (int i=0; i<N; i++){
        for (int j=N-1; j>i; j--){
            if (A[j].value < A[j-1].value){
                Card t=A[j];//A問題ではswapを使っていたが、アルファベットと数値を入れ替えるには、この方法でしかできない！
                A[j]=A[j-1];
                A[j-1]=t;
            }
        }
    }
}

void selection(Card A[],int N){
    for (int i=0; i<N; i++){
        int minj=i;
        for (int j=i; j<N; j++){
            if (A[j].value < A[minj].value) minj=j;
        }
        Card t=A[i];
        A[i]=A[minj];
        A[minj]=t;
    }
}

void print(struct Card A[],int N){
    for (int i=0; i<N; i++){
        if (i>0) cout << " ";
        cout << A[i].suit << A[i].value;
    }
    cout << endl;
}

//バブルソートと選択ソートの結果を比較
bool isStable(Card C1[],Card C2[],int N){
    for (int i=0; i<N; i++){
        if (C1[i].suit!=C2[i].suit) return false;
    }
    return true;
}

int main(){
    Card C1[100],C2[100];
    int N; 
    char ch;

    cin >> N;
    for (int i=0; i<N; i++){
        cin >> C1[i].suit >> C1[i].value;
    }

    for (int i=0; i<N; i++) C2[i]=C1[i];

    bubble(C1,N);
    selection(C2,N);

    print(C1,N);
    cout << "Stable" << endl;

    print(C2,N);
    if (isStable(C1,C2,N)){
        cout << "Stable" << endl;
    }else{
        cout << "Not stable" << endl;
    }
    return 0;
}

2_D(シェルソート)

#include <bits/stdc++.h>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector <int> G;

void insertionSort(int A[],int n,int g){
    for (int i=0; i<n; i++){
        int v=A[i];
        int j=i-g;
        while(j>=0 && A[j]>v){
            A[j+g]=A[j];
            j-=g;
            cnt++;
        }
        A[j+g]=v;
    }
}

void shellSort(int A[],int n){
    //数列G={1,4,13,40,121,364,1093,...}を生成
    for (int h=1; ; ){
        if (h>n) break;
        G.push_back(h);
        h=3*h+1;
    }
    for (int i=G.size()-1; i>=0; i--){
        insertionSort(A,n,G[i]);
    }
}

int main(){
    cin >> n;
    for (int i=0; i<n; i++) cin >> A[i];
    cnt=0;

    shellSort(A,n);

    cout << G.size() << endl;
    for (int i=G.size()-1; i>=0; i--){
        cout << G[i];
        if (i) cout << " ";
    }
    cout << endl;
    cout << cnt << endl;

    for (int i=0; i<n; i++) cout << A[i] << endl;
    return 0;
}