codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
//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 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; }
Private
[
?
]
Run code
Submit