Description

문제정의
• Priority queue를 응용한 Insertion sort의 구현
1. 코드 실행 시 필요한 파라미터를 전달
§ 생성되는 sequence를 결정하는 k, n 값과 정렬 알고리즘에 대한 정보를 main 함수에 인자로 전달
§ Example
• $ ./HW2_2024xxxx 4 20 → k = 4 / n = 20
• $ ./HW2_2024xxxx 10 20 → k = 10 / n = 20
2. k의 배수를 k부터 n개 생성하여 매번 random한 순서로 겹치지 않도록 생성
3. 생성된 n개의 난수를 key로 가지는 노드를 각각 Insertion sort로 enqueue하는 priority queue 만들기
§ 오름차순만 구현
§ insertion 알고리즘에 대해 Array 기반과 Linked-list 기반으로 한 두 가지 버전을 각각 함수로 구현하고, 두 버전의 정렬 시간을 각각 계산
§ n이 10 이하인 경우 sorting 전 / 후의 sequence를 화면에 출력
• before^sort:^3^24^15^6^30^9^12^27^21^18
• after^sort:^3^6^9^12^15^18^21^24^27^30
§ time 라이브러리를 응용하여 sorting 함수가 수행되는 시간을 화면에 출력 (단위: sec)
• [Execution Time]
• Array:^0.000010^sec (^: space, : enter, 소수점 아래 6자리까지 출력)
• Linked-list:^0.000010^sec
문제정의
• Priority queue를 응용한 Insertion sort의 구현 Input 예외처리
§ k는 1이상 10 이하의 값만 입력 가능
§ n은 1이상 300000 이하의 값만 입력 가능
§ 정해진 양식 외 값이 입력되면
“Error:^Invalid^input^entered. ” 메시지 출력
§ 예외처리는 정수값만 입력하여 테스트함 필수 측정 요소
§ k는 4, n이 10일 때 구현 방법이 Array 혹은 Linked-list 기반일 경우 결과
§ k는 4, n의 값이 300, 3000, 30000, 300000인 경우 각 함수의 평균적인 수행시간 비교
Insertion sort $ ./HW2_2021xxxx k n [Execution Time]
Array: xx sec
Linked-list: xx sec
Priority Queue

결과물 제출
• 조교가 검사할 수 있는 source code와 결과보고서 PDF를 제출
ü 제출 방식 : 학번_이름.zip 파일의 형식으로 PLMS 제출
HW2_학번.c (하나의 파일로 코드구현) / HW2_학번.pdf
ü 실험관련 질문은 Q&A 게시판 활용
ü 담당조교 – 이정목 (jungmok@postech.ac.kr)
ü 기재된 양식 외 제출시 패널티 부여
다음 내용을 포함하여 결과보고서 작성
Sec1 . 본인의 source code가 어떤 방식으로 수행이 되는가 설명
§ 전체적인 시스템의 flow, HW2 code에서개선점 등
Sec2. Queue가 정상 동작+ Sorting 알고리즘이 정상 동작하고 있음을 설명
§ 설명을 위한 실행 결과 화면 캡쳐+ 동작설명
Sec3. n값의 변화와 array, linked list의 알고리즘 수행시간 측정, 비교 및 분석
§ array, linked list의 알고리즘 수행시간과 요소 접근시간에 대한 비교 분석 포함
평가지표
동작 점수
Source code의 정상적인 동작 : Array 와 linked-list를 사용해 각 priority queue 구현, Insertion sort의 정상동작등 70
n값의변화에 따른 평균 수행 시간 변화의 결과와 분석 10
Array와 linked-list의 수행 시간 비교와 분석 20
Total 100
# 지정된 입출력 양식을 지키지 않는 경우 경우 감점.
# 표절율(모사율)이 높은 과제 제출시 부정행위로 판단 부정행위 적발 시 이후 과제에서 패널티를 부여하므로 주의 부정행위를 한 자, 도와준 자 모두 해당