Merge Sort

Data Structure 2019. 2. 10. 23:43



#include <stdio.h>
#include "Windows.h"
#include <algorithm>
using namespace std;

const int MAX_SIZE = 500000;

int arr_size;
int ms[MAX_SIZE], qs[MAX_SIZE], stls[MAX_SIZE], buf[MAX_SIZE];

void merge_sort(int* p, int len) {
	if (len < 2)	return;
	int i, j, k, mid;
	mid = (len / 2);
	i = 0, j = mid, k = 0;

	merge_sort(p, mid);
	merge_sort((p + mid), (len - mid));

	while (i < mid && j < len) {
		if (p[i] < p[j]) {
			buf[k++] = p[i++];
		}
		else {
			buf[k++] = p[j++];
		}
	}

	while (i < mid) {
		buf[k++] = p[i++];
	}

	while (j < len) {
		buf[k++] = p[j++];
	}

	for (int i = 0; i < len; ++i) {
		p[i] = buf[i];
	}
}

void qsort(int* p, int left, int right) {
	if (left >= right)	return;
	int l = left - 1;
	int r = right + 1;
	int mid = p[(l + r) / 2];
	while (1) {
		while (p[++l] < mid);
		while (p[--r] > mid);
		if (l >= r)	break;
		int temp = p[l];
		p[l] = p[r];
		p[r] = temp;
	}
	qsort(p, left, l - 1);
	qsort(p, r + 1, right);
}


int main()
{
	arr_size = MAX_SIZE;

	for (int i = 0; i < arr_size; ++i) {
		ms[i] = rand();
		qs[i] = stls[i] = ms[i];
	}

	int quick_sort_begin = GetTickCount();
	qsort(qs, 0, arr_size - 1);
	int quick_sort_end = GetTickCount();

	int merge_sort_begin = GetTickCount();
	merge_sort(ms, arr_size);
	int merge_sort_end = GetTickCount();

	int stl_sort_begin = GetTickCount();
	sort(stls, stls + arr_size);
	int stl_sort_end = GetTickCount();

	printf("my quick sort : %d\n", (quick_sort_end - quick_sort_begin));
	printf("my merge sort : %d\n", (merge_sort_end - merge_sort_begin));
	printf("stl sort : %d\n", (stl_sort_end - stl_sort_begin));
	printf("=====================================\n");

	quick_sort_begin = GetTickCount();
	qsort(qs, 0, arr_size - 1);
	quick_sort_end = GetTickCount();

	merge_sort_begin = GetTickCount();
	merge_sort(ms, arr_size);
	merge_sort_end = GetTickCount();

	stl_sort_begin = GetTickCount();
	sort(stls, stls + arr_size);
	stl_sort_end = GetTickCount();

	printf("my quick sort : %d\n", (quick_sort_end - quick_sort_begin));
	printf("my merge sort : %d\n", (merge_sort_end - merge_sort_begin));
	printf("stl sort : %d\n", (stl_sort_end - stl_sort_begin));
	printf("=====================================\n");

	for (int i = 0; i < arr_size; ++i) {
		if (qs[i] != stls[i] || ms[i] != stls[i]) {
			printf("Error\n");
		}
	}

	return 0;
}


설정

트랙백

댓글

[KOI]전국본선 2014 중등부 세번째 문제






#include <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;

const int MAX_SIZE = 500000;

struct BUS{
	int s, e, index;
};

bool comp(BUS a, BUS b) {
	return (a.s == b.s) ? (a.e > b.e) : (a.s < b.s);
}

bool comp1(BUS a, BUS b) {
	return (a.index < b.index);
}

BUS bus[MAX_SIZE];

int main()
{
	int N, M, end_point = 0;
	scanf("%d %d", &N, &M);
	for(int i = 0; i < M; ++i){
		scanf("%d %d", &bus[i].s, &bus[i].e);
		bus[i].index = i + 1;

		if (bus[i].s > bus[i].e) {
			end_point = max(end_point, bus[i].e);
			bus[i].e += N;
		}
	}

	sort(bus, bus + M, comp);

	deque<BUS> q;
	for (int i = 0; i < M; ++i) {
		if (q.empty() || q.back().e < bus[i].e) {
			q.push_back(bus[i]);
		}
	}

	while (!q.empty() && q.front().e <= end_point) {
		q.pop_front();
	}

	sort(q.begin(), q.end(), comp1);

	for (auto x : q) {
		printf("%d ", x.index);
	}

	return 0;
}


설정

트랙백

댓글

[KOI]전국본선 2014 중등부 두번째 문제




#include <stdio.h>

int seat[2000][2001];

int gcd(int a, int b) {
	return (b) ? gcd(b, a % b) : (a);
}

int main()
{
	int ret = 0;
	int from, to;
	scanf("%d %d", &from, &to);
	for (int i = from; i <= to; ++i) {
		for (int j = 0; j < i; ++j) {
			int g = gcd(i, j);
			int up = j / g;
			int down = i / g;
			if (seat[up][down] == 0) {
				seat[up][down] = 1;
				++ret;
			}
		}
	}
	printf("%d\n", ret);
	return 0;
}


설정

트랙백

댓글

[KOI]전국본선 2013 중등부 두번째 문제




#include <stdio.h>

int main()
{
	int n;
	int after[30] = { 0, }, before[30] = { 0, };
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &after[i]);
	}
	int cur = 0, count = 0;
	while (count < n) {
		while (before[cur] != 0) {
			cur = (cur + 1) % n;
		}
		before[cur] = after[count++];
		cur = (before[cur] + cur) % n;
	}

	printf("%d\n", n);
	for (int i = 0; i < n; ++i) {
		printf("%d ", before[i]);
	}

	return 0;
}


설정

트랙백

댓글

[KOI]전국본선 2013 중등부 첫번째 문제





#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct ANIMAL {
	int y, x;
};

vector<int> hunter;
vector<animal> animal;

bool comp(const ANIMAL& a, const ANIMAL& b) {
	return (a.x < b.x);
}

bool is_kill(const ANIMAL& a, const int h, const int len) {
	int dist = abs(a.x - h) + a.y;
	if (dist <= len)		return true;
	else					return false;
}

int main()
{
	int M, N, L;
	scanf("%d %d %d", &M, &N, &L);

	hunter.resize(M);
	animal.resize(N);

	for (int i = 0; i < M; ++i) {
		scanf("%d", &hunter[i]);
	}

	for (int i = 0; i < N; ++i) {
		scanf("%d %d", &animal[i].x, &animal[i].y);
	}

	sort(hunter.begin(), hunter.end());
	sort(animal.begin(), animal.end(), comp);

	int ret = 0;
	for (auto ani : animal) {
		auto target = lower_bound(hunter.begin(), hunter.end(), ani.x) - hunter.begin();
		if (is_kill(ani, hunter[target], L)) {
			++ret;
		}
		else {
			if (target > 0) {
				--target;
				if (is_kill(ani, hunter[target], L)) {
					++ret;
				}
			}
		}
	}

	printf("%d\n", ret);
	
	return 0;
}


설정

트랙백

댓글