ソート学習

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