[ create a new paste ] login | about

Link: http://codepad.org/IuJQWr1T    [ raw code | output | fork ]

C++, pasted on Oct 16:
//Radix Sort

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

struct CounselingTime //한 학생의 상담 시간을 저장
{
	int start; //상담 시작 시간
	int end; //상담 종료 시간
};

const int studentNumberMax = 100000; //1 <= 학생 수 <= studentNumberMax
const int CounselingTimeMax = (int)pow((double)2, (double)31); // 0 <= 상담 시작 및 종료 시간의 최대값 <= CounselingTimeMax - 1
const int QueueNumber = 10; //10진수를 사용하므로 큐의 개수: 10개
const unsigned int DigitsNumber = 10; //상담 종료 시간의 최댓값의 자릿수: 10자리

void WriteCTL(int& SN, vector<struct CounselingTime>& CTL); //상담 시간 목록의 내용 작성(학생 수를 정하고 각 학생의 상담 시작 및 종료 시간 설정)
void RadixSort(vector<struct CounselingTime>& CTL, queue<struct CounselingTime> Bucket[]); //기수 정렬을 통해 상담 시간 목록의 각 학생의 상담 종료 시간이 오름차순이 되도록 정렬
void WriteCTT(vector<struct CounselingTime>& CTL, vector<struct CounselingTime>& CTT); // 상담 시간표의 내용 작성(최대한 많은 학생과 상담할 수 있는 상담 시간표 작성)
void showCTT(vector<struct CounselingTime>& CTT); //상담 학생 수와 상담 시간표를 출력

int main(int argc, char** argv)
{
	clock_t programStart = clock(); //프로그램 시작 시간
	clock_t sortStart; //정렬 시작 시간
	clock_t sortEnd;  //정렬 종료 시간
	clock_t programEnd; //프로그램 종료 시간

	int studentNumber; //전체 학생 수(SN)
	vector<struct CounselingTime> CounselingTimeList; //상담 시간 목록. 모든 학생의 상담 시작 및 종료 시간을 저장(CTL)
	vector<struct CounselingTime> CounselingTimeTable; //최대한 많은 학생과 상담할 수 있는 상담 시간표 저장(CTT)
	queue<struct CounselingTime> Bucket[QueueNumber]; //기수 정렬을 위한 버킷

	srand((unsigned int)time(NULL)); //난수 생성을 위한 코드

	WriteCTL(studentNumber, CounselingTimeList); //상담 시간 목록의 내용 작성(상담 학생 수를 정하고 각 학생의 상담 시작 및 종료 시간 설정)

	sortStart = clock(); //정렬 시작 시간
	RadixSort(CounselingTimeList, Bucket);//기수 정렬을 통해 상담 시간 목록의 각 학생의 상담 종료 시간이 오름차순이 되도록 정렬
	sortEnd = clock(); // 정렬 종료 시간

	WriteCTT(CounselingTimeList, CounselingTimeTable); // 상담 시간표의 내용 작성(최대한 많은 학생과 상담할 수 있는 상담 시간표 작성)

	showCTT(CounselingTimeTable); //상담 학생 수와 상담 시간표를 출력

	programEnd = clock(); //프로그램 종료 시간

	cout << "전체 학생 수: " << CounselingTimeList.size() << endl; //전체 학생 수 출력
	cout << "상담 학생 수: " << CounselingTimeTable.size() << endl; //상담 학생 수 출력
	cout << "프로그램 실행 시간: " << (double)(programEnd - programStart) / (double)1000 << endl; //프로그램 실행 시간 출력
	cout << "정렬 실행 시간 :" << (double)(sortEnd - sortStart) / (double)1000 << endl; //정렬 실행 시간 출력

	return 0;
}

void WriteCTL(int& SN, vector<struct CounselingTime>& CTL) //상담 시간 목록의 내용 작성(학생 수를 정하고 각 학생의 상담 시작 및 종료 시간 설정)
{
	int studentNumber = rand() % studentNumberMax + 1; //학생 수를 1~studentNumberMax 사이의 값 중 하나로 랜덤 지정

	for (int i = 0; i < studentNumber; i++) //각 학생의 상담 시작 및 종료 시간 설정
	{
		struct CounselingTime tmp;
		tmp.start = rand() % CounselingTimeMax; //한 학생의 상담 시작 시간 저장
		while (true)
		{
			tmp.end = rand() % CounselingTimeMax; //한 학생의 상담 종료 시간 저장
			if (tmp.end >= tmp.start)
			{
				break; //한 학생의 상담 종료 시간 >= 상담 시작 시간이면 정상적인 시간 저장이므로 루프 종료
			}
		}
		CTL.push_back(tmp); //한 학생의 상담 시간을 상담 시간 목록에 저장
	}

	/* 전체 학생 수도 가장 많고 상담 종료 시간도 내림차순으로 설정되어 있는 최악의 경우 계산용으로 쓰일 상담 시간 목록 작성
	int studentNumber = studentNumberMax; //학생 수를 studentNumberMax로 지정

	for (int i = 0; i < studentNumber; i++) //각 학생의 상담 시작 및 종료 시간 설정
	{
		//상담 시작 및 종료 시간을 최댓값부터 1씩 줄여나가며 저장
		int tmpTime = CounselingTimeMax - 1;
		struct CounselingTime tmp;
		tmp.start = tmpTime;
		tmp.end = tmpTime; 
		tmpTime++;

		CTL.push_back(tmp); //한 학생의 상담 시간을 상담 시간 목록에 저장
	}
	*/
}

void RadixSort(vector<struct CounselingTime>& CTL, queue<struct CounselingTime> Bucket[])//기수 정렬을 통해 상담 시간 목록의 각 학생의 상담 종료 시간이 오름차순이 되도록 정렬
{
	for (unsigned int i = 0; i < DigitsNumber; i++) //상담 종료 시간의 최댓값의 자릿수만큼 반복
	{
		for (unsigned int j = 0; j < CTL.size(); j++) //상담 시간 목록의 학생 수만큼 반복
		{
			//상담 종료 시간의 뒤에서 (i + 1)번째 자릿수를 구함
			int digit = CTL[j].end;
			for (unsigned int k = 0; k < i; k++)
			{
				digit /= 10;
			}
			digit %= 10;

			//상담 종료 시간의 뒤에서 (i + 1)번째 자릿수의 값(0~9)에 따라
			//버킷의 알맞은 큐(0~9)에 넣음
			switch (digit)
			{
			case 0:
				Bucket[i].push(CTL[j]);
				break;
			case 1:
				Bucket[i].push(CTL[j]);
				break;
			case 2:
				Bucket[i].push(CTL[j]);
				break;
			case 3:
				Bucket[i].push(CTL[j]);
				break;
			case 4:
				Bucket[i].push(CTL[j]);
				break;
			case 5:
				Bucket[i].push(CTL[j]);
				break;
			case 6:
				Bucket[i].push(CTL[j]);
				break;
			case 7:
				Bucket[i].push(CTL[j]);
				break;
			case 8:
				Bucket[i].push(CTL[j]);
				break;
			case 9:
				Bucket[i].push(CTL[j]);
				break;
			}
		}

		int bucketNumber = 0; //버킷에서 bucketNumber번째 큐를 방문함
		for (unsigned int j = 0; j < CTL.size(); j++) //상담 시간 목록의 학생 수만큼 반복
		{
			if (Bucket[bucketNumber].empty() == true)
			{
				//버킷에서 지금 보고 있는 큐가 비었다면 다음 큐로 넘어감
				bucketNumber++;
				continue;
			}
			//버킷에서 지금 보고 있는 큐의 맨앞에 있는 학생의 상담 시간 정보를 빼내고
			//상담 시간 목록의 j번째 인덱스의 값으로 함
			CTL[j] = Bucket[bucketNumber].front();
			Bucket[bucketNumber].pop();
		}
	}
}

void WriteCTT(vector<struct CounselingTime>& CTL, vector<struct CounselingTime>& CTT) // 상담 시간표의 내용 작성(최대한 많은 학생과 상담할 수 있는 상담 시간표 작성)
{
	CTT.push_back(CTL[0]); //상담 시간 목록의 가장 처음의 내용을 상담 시간표에 추가
	for (unsigned int i = 1; i < CTL.size(); i++) //상담 시간 목록의 내용을 1번 인덱스부터 마지막 인덱스까지 살펴봄
	{
		if (CTL[i].start >= CTT.back().end)
		{
			/*
			상담 시간 목록 i번 인덱스의 상담 시작 시간이 상담 시간표의 마지막 상담 종료 시간보다 이르지 않으면
			상담 시간표에 상담 시간 목록 i번 인덱스의 내용 추가
			*/
			CTT.push_back(CTL[i]);
		}
	}

	return;
}

void showCTT(vector<struct CounselingTime>& CTT) //상담 학생 수와 상담 시간표를 출력
{
	cout << "상담 학생 수: " << CTT.size() << "명" << endl;
	cout << "<상담 시간표>" << endl;
	for (unsigned int i = 0; i < CTT.size(); i++)
	{
		cout << "(" << CTT[i].start << ", " << CTT[i].end << ")" << endl;
	}
	cout << endl;

	return;
}


Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
상담 학생 수: 8명
<상담 시간표>
(1146296421, 1800424283)
(2056391137, 2089495050)
(2100578363, 2125228656)
(2128056468, 2134580154)
(2136095537, 2137617884)
(2144213699, 2144479327)
(2146542228, 2147269115)
(2147442321, 2147474203)

전체 학생 수: 58370
상담 학생 수: 8
프로그램 실행 시간: 100
정렬 실행 시간 :100


Create a new paste based on this one


Comments: