-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path4.html
127 lines (126 loc) · 7.69 KB
/
4.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
<h2>1. 목표</h2>
<p>여러가지 정렬 알고리즘을 구현하고 성능을 비교하면서 알고리즘의 중요성을 깨닫도록 합니다.</p>
<h2>2. 문제</h2>
<p>아래와 같은 여러 가지 정렬 알고리즘을 구현하고 비교해 봅니다.</p>
<ul>
<li>[B] Bubble Sort</li>
<li>[I] Insertion Sort</li>
<li>[H] Heap Sort</li>
<li>[M] Merge Sort</li>
<li>[Q] Quick Sort</li>
<li>[R] Radix Sort</li>
</ul>
<h2>3. 뼈대 코드</h2>
<p><a href="/assignment_skeleton/SortingTest.txt" class="btn btn-primary">뼈대 코드 받기</a></p>
<div class="alert alert-block">
<h4>중요</h4>
이번 숙제는 뼈대 코드를 필히 사용해야 합니다. (같은 입출력 여건에서의 객관적인 비교를 위함)<br>
뼈대 코드를 사용하지 않을 경우 입출력 문제나, 잘못된 시간체크 연산에 의해 불이익을 받을 수 있습니다.<br>
또한 뼈대 코드의 내용을 이해해서 자신의 것으로 만들기 바랍니다.<br>
뼈대 코드의 마지막 부분에 각각의 소팅에 대한 함수가 있습니다. 거기서부터 구현을 시작하면 됩니다.
</div>
<h2>4. 입력 형식<small>숫자 입력 -> 소팅 방법</small></h2>
<ol>
<li>입력은 숫자의 나열로 이루어지며, 첫 줄에 총 숫자의 갯수, 둘째줄부터 각각의 숫자가 입력됩니다.
<div class="example">
<pre>
9 (총 숫자의 갯수)
100
7
925
-234
10
-9999
12738
239
-2391 (여기까지 총 9개)</pre>
</div>
</li>
<li>숫자의 나열 대신 난수를 입력할 수도 있습니다. 이 때는 첫 줄에 r (갯수) (최소값) (최대값) 이 오고 끝납니다.
<div class="example">
<pre>
r 1000 -30000 30000 (-30000 에서 30000 까지(-30000과 30000도 포함) 1000개의 숫자를 랜덤하게 생성하고 그것을 입력으로 대신한다)</pre>
</div>
</li>
<li>숫자의 나열이 정의 되었으면 다음 줄에서 소팅 방법이 입력됩니다.<br>
방법은 B, I, H, M, Q, R (2번 항목의 소팅 종류 참조) 중의 한 글자로 입력됩니다.</li>
<li>소팅 방법이 입력되면 소팅을 수행하고 수행결과를 출력합니다.<br>
출력한 다음 다시 소팅 방법을 입력받습니다. (3번으로 돌아감)<br>
만약 소팅 방법에 X가 입력되었다면 종료합니다.<br>
<strong>모든 숫자는 정수이며 int의 범위 내에 속합니다. 숫자들의 총 갯수는 1000000개 이하입니다.</strong></li>
</ol>
<h2>5. 출력 형식<small>2가지 입력 방법(숫자의 나열 or 난수)에 따라 다르게 출력</small></h2>
<ol>
<li>숫자의 나열이 입력되었다면 정렬된 숫자들을 오름차순(작은값에서 큰값으로) 으로 한 값당 한줄에 출력합니다.(정렬 결과 출력)<br>
(작성한 코드가 정렬을 잘 수행하는지를 확인하고자 하는 목적)
<div class="example">
<pre>
-9999
-2391
-234
7
9
10
100
239
925</pre>
</div>
</li>
<li>난수가 입력되었다면 정렬을 수행하되 결과는 출력할 필요 없고 대신 수행 시간(ms)를 출력합니다.<br>
(작성한 코드가 각각의 정렬 방법에 따라 어느 정도의 시간이 걸리는지를 알아보고자 하는 목적)<br>
뼈대 코드에 구현이 되어 있습니다.</li>
</ol>
<h2>6. 입출력 예제</h2>
<div class="example">
<pre>
$ java SortingTest <- 프로그램 실행
5 <- 이렇게 입력(숫자가 총 5개라는 뜻)
3 <- 이렇게 입력(첫번째 숫자)
1 <- 이렇게 입력(두번째 숫자)
9 <- 이렇게 입력(세번째 숫자)
3 <- 이렇게 입력(네번째 숫자)
4 <- 이렇게 입력(다섯번째 숫자)
Q <- 이렇게 입력(Quick Sort를 수행하라)
1 <- 이렇게 출력(QuickSort로 오름차순 정렬한 첫번째 숫자)
3 <- 이렇게 출력(QuickSort로 오름차순 정렬한 두번째 숫자)
3 <- 이렇게 출력(QuickSort로 오름차순 정렬한 세번째 숫자)
4 <- 이렇게 출력(QuickSort로 오름차순 정렬한 네번째 숫자)
9 <- 이렇게 출력(QuickSort로 오름차순 정렬한 다섯번째 숫자)
B <- 이렇게 입력(Bubble Sort를 수행하라)
1 <- 이렇게 출력(BubbleSort로 오름차순 정렬한 첫번째 숫자)
3 <- 이렇게 출력(BubbleSort로 오름차순 정렬한 두번째 숫자)
3 <- 이렇게 출력(BubbleSort로 오름차순 정렬한 세번째 숫자)
4 <- 이렇게 출력(BubbleSort로 오름차순 정렬한 네번째 숫자)
9 <- 이렇게 출력(BubbleSort로 오름차순 정렬한 다섯번째 숫자)
X <- 이렇게 입력(이제 종료해라)
$ <- 프로그램 종료
$ java SortingTest <- 프로그램 실행
r 100 -200 200 <- 이렇게 입력(숫자가 총 100개이며 범위는 -200 에서 200 사이에서 랜덤하게 생성)
Q <- 이렇게 입력(Quick Sort를 수행하라)
100 ms <- 이렇게 출력(QuickSort를 수행하는데 걸린 시간.)
B <- 이렇게 입력(Bubble Sort를 수행하라)
10000 ms <- 이렇게 출력(BubbleSort를 수행하는데 걸린 시간.)
X <- 이렇게 입력(이제 종료해라)
$ <- 프로그램 종료</pre>
</div>
<h2>7. 보고서</h2>
<p>이번 과제는 여러 정렬 알고리즘을 비교하는 것이 목적이므로 보고서를 받습니다. 보고서는 다음의 내용을 포함해야 합니다.</p>
<ol>
<li>정렬 알고리즘의 동작 방식. 정렬의 경우 실행 결과만으로 알고리즘에 맞게 구현했는지 알 수 없으므로, 이에 대한 설명을 적습니다.</li>
<li>동작 시간 분석. 정렬에 걸린 시간을 측정하고 이를 분석합니다. 특히, data의 개수에 따른 분석은 반드시 포함하도록 합니다.</li>
</ol>
<p>단, 다음의 경우 감점이 될 수 있습니다.</p>
<ol>
<li>분량이 지나치게 많은 경우. 전달하고자 하는 내용을 간결하게 요약하는 것이 중요합니다.</li>
<li>알고리즘 설명 시 다른 곳의 설명을 단순히 복사한 경우. 자신이 알고리즘의 원리를 이해했다는 것을 보여야 합니다.</li>
<li>구현 내용을 일일이 설명하려 하는 경우. 핵심 내용에 대한 설명만 적도록 합니다.</li>
<li>실험 결과를 단순히 나열한 경우. 실험 결과 역시 요약해서 적습니다. 가령 같은 조건에서 여러 번 실험한 경우, 실험 횟수/최대값/최소값/평균/표준편차를 적는 정도로 충분합니다.</li>
</ol>
<h2>8. 참고사항</h2>
<ol>
<li>효율적인 알고리즘 사용 여부가 점수에 영향을 줄 수 있습니다.</li>
<li>수행 시간은 입출력 부분은 빼고 실제 소팅 시간만 재도록 합니다.</li>
<li>교재, 강의노트의 code나 Java 표준 API를 이용해도 좋습니다.(단 5번 주의사항 유의) 하지만 그밖의 것은 직접 만들도록 합니다.</li>
<li><strong>과목 게시판에 과제에 대한 질문 및 주의사항이 공지됩니다. 이를 수시로 확인하시기 바랍니다.</strong></li>
<li><a href="/assignments/cheating">부정행위에 관한 주의사항</a>을 읽기 바랍니다.</li>
</ol>