Help us understand the problem. What is going on with this article?

ソート学習

More than 1 year has passed since last update.
#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 番目の要素を適切な場所へ挿入することを繰り返す
というアルゴリズムです。「41352」に対する動作例はこんな感じです。1 個目の「4」はそのままで、2 個目の「1」を適切な場所まで前に持っていきます。次に 3 個目の「3」を適切な場所まで前に持っていきます。次に 4 個目の「5」を適切な場所まで前に持っていきます (「5」はその手前の4より既に大きいので結局動きません)。最後に 5 個目の「2」を適切な場所まで前に持っていきます。

#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;
    }
};
tell0120xxx
個人的日記
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away