[자료구조]정렬 알고리듬 효율 비교

소개

알고리듬 시간에 배운 각 정렬 알고리듬의 효율을 비교한 레포트이다.

목차

1. 실험목적
2. 실험환경
3. Sort Algorithm과 Code 구현
4. 실험방법
5. 실험결과
6. 결론
7. 참고문헌

본문내용

1. 실험목적
Algorithm 수업 시간에 배운 여러 종류의 sorting algorithm의 효율을 비교한다.
Insertion Sort
Merge Sort
Quick Sort

2. 실험환경
실험환경은 다음과 같다.
CPU : Pentium 4 1.5GHz
Memory: 256 MB
OS : Window 2000
Compiler: Visual C++ 6.0
Language: C++
Data Size: 100~100000 (Uniformly distributed random number)
그러나 각 sort algorithm의 효율이 CPU와 Memory의 영향을 받지 않도록 하기 위하여 프로그램에 각 sort의 실행 횟수를 weight factor를 두어 계산하였다.

3. Sort Algorithm과 Code 구현
3.1 Insertion Sort
삽입정렬(Insertion Sort)은 데이터를 두 개씩 비교하여 (오름차순으로 배열할 시) 작은 것을 앞으로, 큰 것을 뒤로 보내어 정렬하는 방법이다. C++ language를 이용하여 Text (T.C.R. Introduction to Algorithm 2nd Ed.) p.24에 나와있는 algorithm을 구현하면 다음과 같다. 주석 부분이 책에 나온 algorithm 내용이다.

(그림 1. p.24 Insertion Sort 구현)

insertionSort 함수는 parameter로 배열과 배열의 마지막 index를 받아서 배열의 처음부분을 시작으로 오름차순으로 배열할 시에 두 데이터의 크기를 비교하여 두 데이터 중 작은 것을 앞으로 보내고 큰 것을 뒤로 보낸다.

3.2 Merge Sort
Merge Sort는 데이터 전체를 가지고 정렬을 하는 것이 아니라 여러 개의 집합으로 나누고 각 부분을 정렬하여 다시 합치는 divide and conquer 기법을 이용한 Algorithm이다. Merge Sort는 다음과 같은 작업을 반복 수행하면서 정렬한다.
(1) 분할(divide): 입력 데이터를 같은 크기를 가지는 집합 2개로 분할
(2) 정복(conquer): 부분집합의 원소들을 정렬.

참고자료

· 1. C로 배우는 쉬운 자료구조 (이지영 저. 한빛미디어)
· 2. C. C++로 배우는 자료구조론(주우석 저. 한빛미디어)
· 3. The Art of Computer Programming (Donald E. Knuth. Addison-Wesley)
· 4. Numerical Analysis and Graphic Visualization with MATLAB (Shoichiro Nakamura)
· 5. C++ 프로그래밍 (윤성우 저. Freelec)