ソート学習

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int N;
    int a[100000];
    cin >> N;
    for (int i = 0; i < N; ++i)cin >> a[i];
    sort(a, a + N);//a[0;N]を小さい順にソート
    for (int i = 0; i < N; ++i)cout << a[i] << " ";
        return 0;
}

入力として
8
12 66 3 23 51 89 15 37
を与えると出力結果として
3 12 15 23 37 51 66 89
が返ってくる

vectorでもソートすると

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int N;     //要素数
    vector<int>a;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int a_temp;
        cin >> a_temp;
        a.push_back(a_temp);
    }
    sort(a.begin(), a.end());

    for (int i = 0; i < N; ++i)cout << a[i];
}

a.push_back(要素)でaに要素を挿入することができる大きい順にソートしたい時は

sort(a.begin(), a.end(), greater<int>()); 

とすればよい
特殊な比較関数(ここでは50と近い順でやってみる)で比較したい時は

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool cmp(int a, int b) {
    return abs(a - 50) < abs(b - 50);
}
int main(){
    int N;     //要素数
    vector<int>a;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int a_temp;
        cin >> a_temp;
        a.push_back(a_temp);
    }
    sort(a.begin(), a.end(),cmp);

    for (int i = 0; i < N; ++i)cout << a[i];
}

まずは素朴なソートから入って行きます。挿入ソートは、

前から順番に、i 番目の要素を適切な場所へ挿入することを繰り返す
というアルゴリズムです。「４１３５２」に対する動作例はこんな感じです。1 個目の「４」はそのままで、2 個目の「１」を適切な場所まで前に持っていきます。次に 3 個目の「３」を適切な場所まで前に持っていきます。次に 4 個目の「５」を適切な場所まで前に持っていきます (「５」はその手前の４より既に大きいので結局動きません)。最後に 5 個目の「２」を適切な場所まで前に持っていきます。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    /*挿入前の配列を出力してみる*/
    cout << "Before:";
    for (int i=0; i < n; i++)cout << a[i] << " ";
    cout << endl;
    /*挿入ソート*/
    for (int i = 1; i < n; i++) {
        int v = a[i];
    //vを挿入する適切な場所jを探す
    int j = i;
    for (; j > 0; --j) {
        if (a[j - 1] > v) {//vより大きい奴は1個後ろに移す
            a[j] = a[j - 1];
        }
        else break;//v以下になったら止める
    }
    a[j] = v;//最後にj番目にvを挿入
    /*各ステップの配列を出力してみる*/
    cout << "after step" << i << ":";
    for (int i = 0; i < n; i++)cout << a[i] << " ";
    cout << endl;
   }
    return 0;
}

マージソートは、再帰を利用したソートアルゴリズムです。配列を半分に分けて、それぞれをソートしておいて、その 2 つをマージすることを繰り返します。MergeSort(a, left, mid) は配列の左半分をソートして、MergeSort(a, mid, right) は配列の右半分をソートします。そしてそれらをマージします。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void MergeSort(vector<int> &a, int left, int right) {
    if (right - left == 1)return;
    int mid = left + (right - left) / 2;
    //左半分[left,mid)をソート
    MergeSort(a, left, mid);
    //右半分[mid,right)をソート
    MergeSort(a, mid, right);
    //一旦「左」と「右」のソート結果をコピーしておく（右側は左右反転）
    vector<int>buf;
    for (int i = left; i < mid; ++i)buf.push_back(a[i]);
    for (int i = right - 1; i >= mid; --i)buf.push_back(a[i]);
    //マージする
    int iterator_left = 0; //左側のイテレータ
    int iterator_right = (int)buf.size() - 1;//右側のイテレータ
    for (int i = left; i < right; ++i) {
        //左側採用
        if (buf[iterator_left] <= buf[iterator_right]) {
            a[i] = buf[iterator_left++];
        }
        //右側採用
        else {
            a[i] = buf[iterator_right--];
        }
    }
}

int main() {
    int n;//要素数
    cin >> n;
    vector<int>a(n);//整列したい配列ベクトル(サイズをnに初期化)
    for (int i = 0; i < n; ++i) {
        cin >> a[i];//整列したい配列を取得
    }
    /*マージソート*/
    MergeSort(a, 0, n);
    return 0;
}

仕組みはわかるけどコード書くのがまだ慣れないむずい、、

次はクイックソート
QuickSort(a, left, right): 配列 a の left 〜 right 部分 a[left:right] をソートする

right - left == 1 だったらリターンする (要素数 1 なので)
配列 a[left:right] の要素を 1 つ選ぶ (pivot と呼ぶ)
a[left:right] を適切に並び替えて、pivot より左側は pivot 未満、右側は pivot 以上になるようにする (このとき、pivot の来る index を i とする)
QuickSort(a, left, i)
QuickSort(a, i+1, right)
という再帰関数を用意しておいて、

QuickSort(a, 0, n)
を呼ぶ

#include<iostream>
#include<vector>
using namespace std;

void QuickSort(vector<int>&a, int left, int right) {
    if (right - left <= 1)return;
    int pivot_index = (left + right) / 2;
    int pivot = a[pivot_index];
    swap(a[pivot_index], a[right - 1]);

    int i = left;
    for (int j = left; j < right - 1; ++j) {
        if (a[j] < pivot) {
            swap(a[i++], a[j]);
        }
    }
    swap(a[i], a[right - 1]);
    QuickSort(a, left, i);
    QuickSort(a, i + 1, right);
}
int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    QuickSort(a, 0, n);

    return 0;
}

ヒープの実装例

#include<iostream>
#include<vector>
using namespace std;

struct Heap {
    vector<int>heap;
    Heap(){}
    void push(int v) {
        heap.push_back(v);
        int i = (int)heap.size() - 1;
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p] >= v)break;
            heap[i] = heap[p];
            i = p;
        }
        heap[i] = v;
    }
    int top() {
        if (!heap.empty())return heap[0];
        else return -1;
    }
    void pop() {
        if (heap.empty())return;
        int v = heap.back();
        heap.pop_back();
        int i = 0;
        while (i * 2 + 1 < (int)heap.size()) {
            int child1 = i * 2 + 1, child2 = i * 2 + 2;
            if (child2 < (int)heap.size() && heap[child2] > heap[child1])child1 = child2;
            if (heap[child1] <= v)break;
            heap[i] = heap[child1];
            i = child1;
        }
        heap[i] = v;
    }
};