# 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;
}
};