バブルソート, 選択ソート, 安定なソート, シェルソート

##[ALDS1_2_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_A)
###バブルソート
教育機関で最初に習ったソート。
計算量はO(N^2)。
バブルソートは、配列は「ソート済みの部分列」と「未ソートの部分列」とに分ける。
配列の末尾から隣接する要素を順番に比べていき、大小関係が逆ならば交換する。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;

int main(int argc, const char * argv[]) {
    int n, ans=0;
    cin >> n;
    
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }
    
    rep(i, n){
        for(int j=n-1; j>i; j--){
            if(A[j-1] > A[j]){
                swap(A[j-1], A[j]);
                ans++;
            }
        }
    }
    
    rep(i, n){
        if(i==n-1) cout << A[i] << endl;
        else cout << A[i] << ' ';
    }
    cout << ans <<  endl;
    
    return 0;
}
```

##[ALDS1_2_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_B)
###選択ソート
計算量はO(N^2)。
未ソートの部分から最小の要素の位置を特定する。
最小の要素の位置にある要素と未ソートの部分の先頭要素を交換する。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;

int main(int argc, const char * argv[]) {
    int n, ans=0;
    cin >> n;
    
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }
    
    rep(i, n){
        int minv=i;
        for(int j=i; j<n; j++){
            if(A[j] < A[minv]){
                minv = j;
            }
        }
        if(minv != i){
            swap(A[i], A[minv]);
            ans++;
        }
    }
    
    rep(i, n){
        if(i==n-1) cout << A[i] << endl;
        else cout << A[i] << ' ';
    }
    cout << ans <<  endl;
    
    return 0;
}
```

##[ALDS1_2_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_C)
###安定なソート
ここでの安定とは、同じ数字がソート後に同じ順番で表示されているかを判定する。
同じ順番なら安定、異なるなら非安定。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;

int main(int argc, const char * argv[]) {
    int n, ans=0;
    cin >> n;
    
    vector<pair<char,int>> A(n);
    vector<pair<char,int>> B(n);
    
    rep(i, n){
        char buf[3];
        cin >> buf;
        
        pair<char,int> p;
        p.first = buf[0];
        p.second = buf[1] - '0';
        A[i] = B[i] = p;
    }
    
    rep(i, n){
        for(int j=n-1; j>i; j--){
            if(A[j-1].second > A[j].second){
                swap(A[j-1], A[j]);
                ans++;
            }
        }
    }
    
    rep(i, n){
        if(i==n-1) cout << A[i].first << A[i].second << endl;
        else cout << A[i].first  << A[i].second << ' ';
    }
    cout << "Stable" <<  endl;
    
    rep(i, n){
        int minv=i;
        for(int j=i; j<n; j++){
            if(B[j].second < B[minv].second){
                minv = j;
            }
        }
        if(minv != i){
            swap(B[i], B[minv]);
            ans++;
        }
    }
    
    rep(i, n){
        if(i==n-1) cout << B[i].first << B[i].second << endl;
        else cout << B[i].first << B[i].second << ' ';
    }
    
    string s = "Stable";
    rep(i, n){
        if(A[i].first != B[i].first) s = "Not stable";
    }
    cout << s <<  endl;
    
    return 0;
}
```

##[ALDS1_2_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_D)
###Shell Sort
次のプログラムは、挿入ソートを応用してN個の整数を含む数列Aを昇順に整列するプログラムです。
任意のG[g１、g２、g３]をm個だけ作成し、g１、...gn毎に挿入ソートを行う。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;

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

void ShellSort(vector<int> A, int n){
    int cnt=0;
    int m=0;
    vector<int>G;
    
    for(int i=(n+1)/2; i>0; i=i/2){
        G.push_back(i);
        m++;
    }
    
    for(int i=0; i<m; i++){
        InsertSort(A, n, G[i], cnt);
    }
    
    cout << m << endl;
    for(int i=0; i<m; i++){
        if(i==m-1) cout << G[i] << endl;
        else cout << G[i] << ' ';
    }
    cout << cnt << endl;
    for(int i=0; i<n; i++){
        cout << A[i] << endl;
    }
}

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    vector<int> A(n);
    
    rep(i, n){
        cin >> A[i];
    }
    
    ShellSort(A, n);
    
    return 0;
}
```