연재 차례
1. C언어 소개
2. 형태, 연산자, 표현
3. 제어 흐름
4. 함수와 프로그램 구조
5. 포인터와 배열
6. 구조체
7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개
컴퓨팅에서 정렬(sorting) 알고리즘은 어떤 집합의 요소들을 특정한 순서에 위치시키는 것이다. 순서는 숫자적인 순서를 가장 많이
사용한다. 정렬을 효율적으로 하면 탐색과 같은 알고리즘을 최적화 하는데 많은 도움을 주며, 또한 출력된 데이터를 사람이 판독하기
쉽도록 해준다. 컴퓨팅이 시작되면서부터 정렬은 중요한 연구대상 이었다. 1956년에 Bubble sort가 출현한 것을
시작으로 현재 다양한 정렬 알고리즘들이 발명되고 있으며 최근(2004년)에는 Library sort가 발표되었다. 아래는 지금까지
발표된 정렬 알고리즘들 중 에서 대표적인 것들의 종류와 특징을 표로 정리한 것이다.
Bubble sort
Bubble sort는 간단한 정렬 알고리즘이며 서로 인접한 것끼리 비교하면서 정렬 순서가 맞지 않으면 교환하는 방식으로 정렬한다. 정렬 대상을 처음부터 끝까지 비교하면서 더 이상 교환할 것이 없다면 모두 정렬된 것이다. 아래는 Bubble sort 알고리즘을 C언어로 코딩한 것이다.
Insertion sort는 간단한 정렬 알고리즘이며 정렬 대상이 소량일 때 효율적이다. 반대로 정렬 대상이 대량일 때는 Quick sort, Heap sort, Merge sort에 비해서 비효율적이다. 아래는 Insertion sort의 장점을 정리한 것이다.
장 점
- 구현하기가 간단하다.
- 소량의 데이터 집합에 대해서 효율적이다.
- 입력 데이터가 이미 정렬된 순서라면 시간 복잡도가 O(n)으로 효율적이다.
- 정렬 시 필요한 추가적인 공간인 O(1)만 있으면 되므로 메모리 낭비가 없다.
- 사람들이 손에 쥐고 있는 카드들을 순서대로 정렬하는 방법은 Insertion sort와 유사하다.
다음은 Insertion sort 알고리즘을 C언어로 코딩한 것이다.
Merge sort는 비교방식의 알고리즘으로 O(n log n) 효율성을 가지며 분할 정복(Divide and Conquer)으로 동작한다. Merge sort는 1945년도에 John von Neumann에 의해 발명되었다. Merge sort의 정렬방식을 정리하면 다음과 같다.
- 정렬되지 않은 리스트를 반으로 나눈다.
- 반으로 나눈 리스트들을 각각 정렬하는 작업을 재귀적으로 반복한다.
- 반으로 나누어져 정렬된 리스트들을 하나로 합치는 작업을 재귀적으로 반복한다.
다음 그림은 이러한 과정을 설명하는 것이다.
다음은 Merge sort 알고리즘을 C언어로 코딩한 것이다
Quick sort 알고리즘은 1960년에 모스크바 주립 대학교 학생인 Tony Hoare에 의해서 개발되었다. 그 당시 Tony Hoare는 국가 물리 연구소에서 러시아와 영어를 기계 번역하는 프로젝트에 참여 했었는데, 번역된 단어들을 정렬하기 위해서 이 알고리즘을 개발했다. 이 알고리즘을 사용하여 러시아-영어 단어 사전을 구축하여 자기 테이프에 저장했다.
Quick sort는 n개의 요소들을 정렬하는데 평균적으로 O(n x log n)의 효율성을 가지며 다른 알고리즘들에 비해 빠르다. 또한 Quick sort의 순차적이고 지역적인 메모리 참조로 인해서 캐시와도 잘 동작한다. Quick sort는 내부(in-place)정렬로 구현될 수 있으므로 추가적인 공간을 필요로 하지 않으며 “partition-exchange sort”로도 알려져 있다. 분할 정복(divide and conquer)알고리즘인 Quick sort는 정렬대상 리스트를 반으로 나누는 작업을 재귀적으로 반복하면서 정렬하는 방식이다.
정렬 과정 요약설명
리스트에서 pivot에 해당하는 요소를 찾는다. pivot를 기준으로 리스트의 왼쪽에는 pivot보다 작은 값을 오른쪽에는 pivot보다 큰 값을 위치시킨다. 이렇게 만드는 과정을 partition 이라 한다. partitioning 하면 pivot을 기준으로 리스트가 왼쪽과 오른쪽으로 나누어지며, 이렇게 나눈 요소들을 정렬한다. 리스트를 더 이상 나눌 수 없을 때까지 partitioning 작업을 재귀적으로 반복하면 정렬이 완료된다. 이 과정을 아래의 그림을 통해서 시각적으로 확인해 볼 수 있다.
Shell sort는 1959년에 이 알고리즘을 발표한 Donald Shell의 이름에서 유래 되었다. Shell sort는 Insertion sort을 일반화한 것이며 정렬대상 자료가 이미 정렬된 순서대로 입력되면 아주 효율적으로 동작한다. Shell sort는 서로 멀리 떨어져 있는 요소들의 비교와 교환을 가능 하도록 하여 Insertion sort을 향상 시켰다.
다음은 Shell sort 알고리즘을 C언어로 코딩한 것이다.
Heap sort는 선택적인 정렬을 아주 효과적으로 수행한다. Heap sort는 리스트에서 가장 큰 요소를 선택하여 리스트의 끝에 위치 시킨다.(반대로 가장 작은 요소를 선택하여 리스트의 처음에 위치 시킨다) 이 작업을 반복하여 정렬을 완료하는데, 이때 이진 트리와 유사한 힙(heap)이라는 자료 구조를 효과적으로 사용한다. 데이터가 heap에 추가될 때 마다 루트 노드는 가장 큰 요소가 된다. (역으로 가장 작은 요소가 된다) 데이터가 heap에서 삭제될 때도 루트 노드에 가장 큰 요소가 오도록 재배열 시킨다. heap을 사용하면 데이터를 정렬된 순서대로 출력하는데 O(n log n) 만큼 소요되므로 아주 효율적인 알고리즘이다.
다음은 Heap sort 알고리즘을 C언어로 코딩한 것이다.
지금까지 기술한 정렬 알고리즘들의 특징을 표로 요약하면 아래와 같다.
필 / 자 / 소 / 개
※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ Techworld, Inc. 무단전재 및 재배포 금지
| 번호 | 제목 | 작성 | 조회수 |
|---|---|---|---|
| 394 | [C언어와 알고리즘] 진보된 알고리즘 소개- 인공지능 ② (15) | 2012-08-17 | 2022 |
| 393 | [C언어와 알고리즘] 진보된 알고리즘 소개- 인공지능 ① (14) | 2012-08-17 | 2272 |
| 392 | [C언어와 알고리즘] 해싱(Hash) 실습 (13) | 2012-08-17 | 2881 |
| 391 | [C언어와 알고리즘] 트리(Tree) 실습 (12) | 2012-08-17 | 3934 |
| 390 | [C언어와 알고리즘] 리스트(List) 실습 (11) | 2012-08-17 | 5543 |
| 389 | [C언어와 알고리즘] 큐(Queue) 실습 (10) | 2012-08-17 | 4801 |
| 388 | [C언어와 알고리즘] 스택(Stack) 실습 (9) | 2012-08-17 | 4008 |
| 387 | [C언어와 알고리즘] 소팅을 통한 알고리즘 분석 (8) | 2012-08-17 | 2429 |
| 386 | [C언어와 알고리즘] 알고리즘 소개 (7) | 2012-08-17 | 2073 |
| 385 | [C언어와 알고리즘] 구조체 (6) | 2012-08-17 | 3926 |
0개 댓글