퀵소트 저격하기

퀵소트가 O(n log n) 이라고 믿고있는, 지혜가 부족한 사람들을 위해서

 

저격 TC를 생성하는 코드를 올려보고자 한다.

 

 

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

이 문제가 O(n log n) 정렬 문제에서 가장 기초가 되는 문제일텐데

 

이 기초적인 문제에 퀵소트 저격 TC를 추가하면

 

공부를 하는 사람들이 '참교육'을 당할테니

 

아주 교육적인 데이터 되시겠다.

 

 

 

일단 급한대로 정리 안된 코드를 올린다.

rand 가 복잡한 이유는, gcc rand 랑 visual studio rand가 동작방식이 다르기 때문에

부득이하게 gcc에서 사용하는 rand 함수를 이식해왔다.

#include < stdio.h >
#include < stdlib.h >
#include <time.h>
#include<algorithm>
using namespace std;
/* x**31 + x**3 + 1.  */
#define TYPE_3          3
#define BREAK_3         128
#define DEG_3           31
#define SEP_3           3
static int randtbl[DEG_3 + 1] =
{
  TYPE_3,

  -1726662223, 379960547, 1735697613, 1040273694, 1313901226,
  1627687941, -179304937, -2073333483, 1780058412, -1989503057,
  -615974602, 344556628, 939512070, -1249116260, 1507946756,
  -812545463, 154635395, 1388815473, -1926676823, 525320961,
  -1009028674, 968117788, -123449607, 1284210865, 435012392,
  -2017506339, -911064859, -370259173, 1132637927, 1398500161,
  -205601318,
};
static struct random_data
{
	/* FPTR and RPTR are two pointers into the state info, a front and a rear
	   pointer.  These two pointers are always rand_sep places apart, as they
	   cycle through the state information.  (Yes, this does mean we could get
	   away with just one pointer, but the code for random is more efficient
	   this way).  The pointers are left positioned as they would be from the call:
			initstate(1, randtbl, 128);
	   (The position of the rear pointer, rptr, is really 0 (as explained above
	   in the initialization of randtbl) because the state table pointer is set
	   to point to randtbl[1] (as explained below).)  */

	int *fptr = &randtbl[SEP_3 + 1];
	int *rptr = &randtbl[1];

	/* The following things are the pointer to the state information table,
	   the type of the current generator, the degree of the current polynomial
	   being used, and the separation between the two pointers.
	   Note that for efficiency of random, we remember the first location of
	   the state information, not the zeroth.  Hence it is valid to access
	   state[-1], which is used to store the type of the R.N.G.
	   Also, we remember the last location, since this is more efficient than
	   indexing every time to find the address of the last element to see if
	   the front and rear pointers have wrapped.  */

	int *state = &randtbl[1];

	int rand_type = TYPE_3;
	int rand_deg = DEG_3;
	int rand_sep = SEP_3;

	int *end_ptr = &randtbl[sizeof(randtbl) / sizeof(randtbl[0])];
};
int __random_r(struct random_data *buf, int *result)
{
	int *state;


	state = buf->state;

	{
		int *fptr = buf->fptr;
		int *rptr = buf->rptr;
		int *end_ptr = buf->end_ptr;
		unsigned int val;

		val = *fptr += (unsigned int)*rptr;
		/* Chucking least random bit.  */
		*result = val >> 1;
		++fptr;
		if (fptr >= end_ptr)
		{
			fptr = state;
			++rptr;
		}
		else
		{
			++rptr;
			if (rptr >= end_ptr)
				rptr = state;
		}
		buf->fptr = fptr;
		buf->rptr = rptr;
	}
	return 0;
}
random_data rdata;
int rand() {
	int result;
	__random_r(&rdata, &result);
	return result;
}
void my_init() {
	rdata.fptr = &randtbl[SEP_3 + 1];
	rdata.rptr = &randtbl[1];

	rdata.rand_type = TYPE_3;
	rdata.rand_deg = DEG_3;
	rdata.rand_sep = SEP_3;

	rdata.state = &randtbl[1];

	rdata.end_ptr = &randtbl[sizeof(randtbl) / sizeof(randtbl[0])];
}

#define MAX 1000000
#define TEST 0
int n;
int cnt;
struct A {
	int v;
	int i;
	bool operator <(const A &z) {
		return v < z.v;
	}
	bool operator <=(const A &z) {
		return v <= z.v;
	}
	bool operator >(const A &z) {
		return v > z.v;
	}
	bool operator >=(const A &z) {
		return v >= z.v;
	}
	bool operator ==(const A &z) {
		return v == z.v;
	}
	bool operator !=(const A &z) {
		return v != z.v;
	}
}a[MAX];
int b[MAX];

void quickSort(A input[], int first, int last)
{
	int pivot;
	int i;
	int j;
	A temp;

	if (first < last)
	{
		int k;
#if TEST
		//	int k = (rand() % (hi - lo + 1) + lo);
		k = first + rand() % (last - first + 1);
		pivot = input[k].v;
		printf("%d %d  %d\n", first, last, pivot);
#else
		//int k = (rand() % (hi - lo + 1) + lo);
		k = first + rand() % (last - first + 1);
		input[k].v = cnt++;
#endif
		swap(input[first], input[k]);

		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (input[i] <= input[pivot] && i < last)
			{
				i++;
			}
			while (input[j] > input[pivot])
			{
				j--;
			}
			if (i < j)
			{
				temp = input[i];
				input[i] = input[j];
				input[j] = temp;
			}
		}

		temp = input[pivot];
		input[pivot] = input[j];
		input[j] = temp;

		quickSort(input, first, j - 1);
		quickSort(input, j + 1, last);
	}
}

void quickSort2(A input[], int first, int last)
{
	int pivot;
	int i;
	int j;
	A temp;

	if (first < last)
	{
		if (last - first + 1 >= 3) {
			int mid = (first + last) / 2;
#if TEST
			printf("%d %d  %d\n", first, last, mid);
#else
			if (input[first].v == MAX + 1) {
				input[first].v = cnt++;
			}
			if (input[mid].v == MAX + 1) {
				input[mid].v = cnt++;
			}
			if (input[last].v == MAX + 1) {
				input[last].v = cnt++;
			}
#endif
			if (input[first] > input[mid]) swap(input[first], input[mid]);
			if (input[mid] > input[last]) swap(input[mid], input[last]);
			if (input[first] > input[mid]) swap(input[first], input[mid]);
			swap(input[first], input[mid]);
		}

		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (input[i] <= input[pivot] && i < last)
			{
				i++;
			}
			while (input[j] > input[pivot])
			{
				j--;
			}
			if (i < j)
			{
				temp = input[i];
				input[i] = input[j];
				input[j] = temp;
			}
		}

		temp = input[pivot];
		input[pivot] = input[j];
		input[j] = temp;

		quickSort2(input, first, j - 1);
		quickSort2(input, j + 1, last);
	}
}

void quickSort3(A input[], int first, int last)
{
	int pivot;
	int i;
	int j;
	A temp;

	if (first < last)
	{
		int k;
#if TEST
		//	int k = (rand() % (hi - lo + 1) + lo);
		k = (first + last) / 2;
		pivot = input[k].v;
		printf("%d %d  %d\n", first, last, pivot);
#else
		//int k = (rand() % (hi - lo + 1) + lo);
		k = (first + last)/2;
		input[k].v = cnt++;
#endif
		swap(input[first], input[k]);

		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (input[i] <= input[pivot] && i < last)
			{
				i++;
			}
			while (input[j] > input[pivot])
			{
				j--;
			}
			if (i < j)
			{
				temp = input[i];
				input[i] = input[j];
				input[j] = temp;
			}
		}

		temp = input[pivot];
		input[pivot] = input[j];
		input[j] = temp;

		quickSort3(input, first, j - 1);
		quickSort3(input, j + 1, last);
	}
}
int main(void)
{
	my_init();
	int test_case;
	int T = 3;
	int data_list[4] = {
		0,
		15375829,
		15375831,
		15375936,
	};
	for (test_case = 1; test_case <= T; ++test_case)
	{
		char i1x[99];
		char i2x[99];
		char o1x[99];
		char o2x[99];
		sprintf(i1x, "%d_01.in", data_list[test_case]);
		sprintf(i2x, "%d_02.in", data_list[test_case]);
		sprintf(o1x, "%d_01.out", data_list[test_case]);
		sprintf(o2x, "%d_02.out", data_list[test_case]);
		FILE *i1;
		FILE *i2;
		FILE *o1;
		FILE *o2;
#if TEST
		i1 = fopen(i1x, "rb");
		fscanf(i1, "%d", &n);
#else
		n = 500000;
		i1 = fopen(i1x, "wb");
		i2 = fopen(i2x, "wb");
		o1 = fopen(o1x, "wb");
		o2 = fopen(o2x, "wb");
		printf("%d\n", n);
		fprintf(i1, "%d%c", n, 10);
		fprintf(i2, "%d%c", n, 10);
#endif
		for (int i = 0; i < n; i++) {
#if TEST
			fscanf(i1,"%d", &a[i].v);
#else
			a[i].v = MAX + 1;
#endif
			a[i].i = i;
		}
		cnt = 1;
		if (test_case == 1) {
			quickSort(a, 0, n - 1);
		}
		else if (test_case == 2) {
			quickSort2(a, 0, n - 1);
		}
		else {
			quickSort3(a, 0, n - 1);
		}
#if TEST
		for (int i = 0; i < n; i++)
			printf("%d ", a[i].v);
		printf("\n");
		fclose(i1);
#else
		for (int i = 0; i < n; i++)
		{
			if (a[i].v == MAX + 1)
				a[i].v = cnt++;
			b[a[i].i] = a[i].v;
		}
		for (int i = 0; i < n; i++)
		{
			//printf("%d\n", b[i]);
			fprintf(i1, "%d%c", b[i], 10);
			fprintf(i2, "%d%c", n + 1 - b[i], 10);
			fprintf(o1, "%d%c", i + 1, 10);
			fprintf(o2, "%d%c", n - i, 10);
		}
		fclose(i1);
		fclose(i2);
		fclose(o1);
		fclose(o2);
#endif
	}
	return 0;
}

 

아래는 해당 방식을 통해 저격한 데이터 일부이다.

 

아오 회사 네트워크로는 파일 업로드가 안된다..ㅠㅠ 누가 대신 만들어주면 안되나..