알고리즘 정렬(Sort)과 실행시간, 각 정렬 함수의 시간 측정 결과

소개글

알고리즘 정렬(Sort)과 실행시간, 각 정렬 함수의 시간 측정 결과에 대한 보고서 자료입니다.

목차

1. 정렬이란?
2. 정렬 알고리즘의 종류와 구현
(1) 삽입 정렬
(2) 거품 정렬
(3) 병합 정렬
3. 각 정렬 함수의 시간 측정 결과
(1) 이미 정렬된 파일의 경우 실행 시간의 비교
(2) 난수 배열에 대한 실행 시간의 비교
(3) 반쯤 정렬된 배열에 대한 실행 시간의 비교
(4) 역순 배열을 정렬하는데 걸리는 실행 시간의 비교
(5) 마지막으로 각 정렬 알고리즘의 평균 실행시간에 대해 정리해 보자.

본문내용

것 또한 알 수 있다.
(2) 난수 배열에 대한 실행 시간의 비교
N
100
500
1000
2000
5000
7000
10000
선택
2
47
186
736
4578
8963
18279
삽입
2
43
178
713
4382
8585
17645
거품
5
116
474
1905
11799
23125
47397
쉘
1
6
13
31
92
139
206
퀵
0
2
5
10
29
40
59
병합
1
5
10
22
64
88
138
힙
1
6
13
30
82
118
175
난수 배열에 대한 속도측정은 평균적인 경우의 실행 시간이라 할 수 있어 매우 중요한 척도라고 볼 수 있다. 난수 배열에 대해서 퀵 정렬이 가장 뛰어나며 기타 의 성능을 가지는 정렬 방법들이 유효하다.
(3) 반쯤 정렬된 배열에 대한 실행 시간의 비교
N
100
500
1000
2000
5000
7000
10000
선택
2
47
186
736
4576
8960
18273
삽입
2
39
157
724
1375
1833
2573
거품
4
105
437
1741
3963
5482
7843
쉘
0
5
12
22
68
100
150
퀵
1
2
5
89
170
183
204
병합
1
4
10
22
66
91
141
힙
1
6
14
23
71
107
163
삽입 정렬과 거품 정렬의 실행 시간은 여전히 느리다는 것을 알 수 있고, 퀵 정렬과 쉘 정렬, 병합 정렬이 뛰어난 성능을 보인다.
(4) 역순 배열을 정렬하는데 걸리는 실행 시간의 비교
N
100
500
1000
2000
5000
7000
10000
선택
3
69
276
1101
6868
13458
27462
삽입
3
88
352
1408
8792
17229
35163
거품
7
189
756
3023
18899
37044
75602
쉘
1
4
10
20
56
84
130
퀵
1
2
3
8
23
32
48
병합
0
4
10
21
64
89
137
힙
1
6
13
28
79
114
169
선택, 삽입, 거품 정렬은 최악의 경우를 나타낸다. 반면 퀵 정렬과 쉘 정렬은 뛰어난 성능을 보이는 것을 알 수 있다. 나머지 알고리즘들도 입력 자료에 둔감하기 때문에 여전히 효율이 좋다.
(5) 마지막으로 각 정렬 알고리즘의 평균 실행시간에 대해 정리해 보자.
정렬 방법
평균 실행 시간
정렬 방법
평균 실행 시간
삽입 정렬(Insertion)
퀵 정렬(Quick)
쉘 정렬(Shell)
팩 정렬(Heap)
버블 정렬(Bubble)
기수 정렬(Radix)
선택 정렬(Selection)
병합 정렬(2-way Merge)
가장 빠른 속도를 나타내는 것은 기수 정렬이다. 하지만 많은 메모리를 필요로 한다는 점은 알고리즘 선택에 고려를 해야 하는 요소이다. 나머지 기본적인 알고리즘들은 추가적인 메모리가 필요 없지만 속도는 느리다. 속도가 빠르면서 추가적인 메모리가 전혀 필요 없는 방법은 힙 정렬과 쉘 정렬인 것을 알 수 있다. 약간의 스택을 이용할 수 있다면 퀵 정렬도 고려해 볼 만하다. 참고로 병합 정렬은 알고리즘 중에서 유일하게 안정성이 있다는 것을 알아두자.

키워드

알고리즘,   정렬,   sort,   실행시간