Homework #3
컴퓨터과학전공, 문양세
1. 합병정렬과 빠른정렬 경연(competition)
입력 데이터
입력: 0~2147483647 사이의 정수(long type) 값이 한 줄에 5개씩 저장된 파일 (단, 동일 숫자가 중복하여 나타날 수 있음)
출력: 입력 파일의 정수들을 정렬한 후 출력 파일에 동일 형식으로 저장함
입력 파일 예제 (출력 파일도 동일한 형식이어야 함)
프로그래밍 및 동작 환경
프로그래밍 언어: C언어
컴퓨터: cs1.kangwon.ac.kr (Linux 환경)
컴파일러: gcc, 최적화 컴파일 허용
시간측정 방법: gettimeofday() 함수 사용
(파일 입출력 시간 제외하고 순수하게 정렬에 걸린 시간을 측정함)
경연 방법
입력파일: 7,000,000개, 70,000,000개 파일 각 2개씩
(샘플파일: /home/ysmoon/alg‐data/sample.250K, sample.1M)
수행방법: 각 입력 파일에 대한 시간을 스스로 측정하되, 수행시간이 2분(120초)을 초과할 시 강제(^C)로 수행 중단 (교수가 각 수행시간을 기록함)
참고1: 합병정렬과 빠른정렬을 각각 측정하여 비교함
참고2: 정렬의 정확성을 프로그램으로 검증할 예정임
경연 날짜: 4월 11일(목)
강의 시작 전 컴퓨터에 경연준비 완료 필수!
경연은 7분 이내에 완료할 수 있도록 준비 완료할 것!
준비 미비, 시간 초과 등은 감점 요인임!
2. 버블정렬, 합병정렬, 빠른정렬 알고리즘 비교 발표(presentation)
세 가지 알고리즘을 각각 프로그래밍 한다. (언어 제한하지 않음)
다음 변수(파라미터)를 달리하면서 실제 정렬속도를 측정하고 비교한다.
입력(키)의 개수(n)를 달리한다.
컴퓨터 종류(기종, 메모리, CPU 등)를 달리한다.
기타 여러 상황(하이브리드 알고리즘 등)을 달리한다. 추가점수
주의 사항
발표시간: 데모포함 발표시간은 총 10분 이내 (발표시간 엄수)
강의시작 전에 발표 준비 완료할 것 (발표준비 미비한 조는 감점)
제출물: 보고서(프로그램 설계 및 주요코드, 결과 및 분석), 발표 자료
발표일: 4월15일(월): 1조‐5조, 4월18일(목): 6조‐9조
