2011


글: 정재준 (rgbi3307@nate.com ) / 커널연구회(www.kernel.bz)   2011-06-08



연재 차례

 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가 발표되었다. 아래는 지금까지 발표된 정렬 알고리즘들 중 에서 대표적인 것들의 종류와 특징을 표로 정리한 것이다.

위의 정렬 알고리즘들을 C언어 코드와 함께 자세히 알아보도록 하자.


Bubble sort
Bubble sort는 간단한 정렬 알고리즘이며 서로 인접한 것끼리 비교하면서 정렬 순서가 맞지 않으면 교환하는 방식으로 정렬한다. 정렬 대상을 처음부터 끝까지 비교하면서 더 이상 교환할 것이 없다면 모두 정렬된 것이다. 아래는 Bubble sort 알고리즘을 C언어로 코딩한 것이다.

Insertion sort
Insertion sort는 간단한 정렬 알고리즘이며 정렬 대상이 소량일 때 효율적이다. 반대로 정렬 대상이 대량일 때는 Quick sort, Heap sort, Merge sort에 비해서 비효율적이다. 아래는 Insertion sort의 장점을 정리한 것이다.
장 점
- 구현하기가 간단하다.
- 소량의 데이터 집합에 대해서 효율적이다.
- 입력 데이터가 이미 정렬된 순서라면 시간 복잡도가 O(n)으로 효율적이다.
- 정렬 시 필요한 추가적인 공간인 O(1)만 있으면 되므로 메모리 낭비가 없다.
- 사람들이 손에 쥐고 있는 카드들을 순서대로 정렬하는 방법은 Insertion sort와 유사하다.
다음은 Insertion sort 알고리즘을 C언어로 코딩한 것이다.

Merge sort
Merge sort는 비교방식의 알고리즘으로 O(n log n) 효율성을 가지며 분할 정복(Divide and Conquer)으로 동작한다. Merge sort는 1945년도에 John von Neumann에 의해 발명되었다.  Merge sort의 정렬방식을 정리하면 다음과 같다.

- 만약 정렬 대상 리스트의 길이가 0 또는 1 이면 이미 정렬된 것이다.
- 정렬되지 않은 리스트를 반으로 나눈다.
- 반으로 나눈 리스트들을 각각 정렬하는 작업을 재귀적으로 반복한다.
- 반으로 나누어져 정렬된 리스트들을 하나로 합치는 작업을 재귀적으로 반복한다.

다음 그림은 이러한 과정을 설명하는 것이다.
다음은 Merge sort 알고리즘을 C언어로 코딩한 것이다


Quick sort
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 작업을 재귀적으로 반복하면 정렬이 완료된다. 이 과정을 아래의 그림을 통해서 시각적으로 확인해 볼 수 있다.

다음은 Quick sort 알고리즘을 C언어로 코딩한 것이다.


Shell sort
Shell sort는 1959년에 이 알고리즘을 발표한 Donald Shell의 이름에서 유래 되었다. Shell sort는 Insertion sort을 일반화한 것이며 정렬대상 자료가 이미 정렬된 순서대로 입력되면 아주 효율적으로 동작한다. Shell sort는 서로 멀리 떨어져 있는 요소들의 비교와 교환을 가능 하도록 하여 Insertion sort을 향상 시켰다.

다음은 Shell sort 알고리즘을 C언어로 코딩한 것이다.


Heap sort
Heap sort는 선택적인 정렬을 아주 효과적으로 수행한다. Heap sort는 리스트에서 가장 큰 요소를 선택하여 리스트의 끝에 위치 시킨다.(반대로 가장 작은 요소를 선택하여 리스트의 처음에 위치 시킨다) 이 작업을 반복하여 정렬을 완료하는데, 이때 이진 트리와 유사한 힙(heap)이라는 자료 구조를 효과적으로 사용한다. 데이터가 heap에 추가될 때 마다 루트 노드는 가장 큰 요소가 된다. (역으로 가장 작은 요소가 된다) 데이터가 heap에서 삭제될 때도 루트 노드에 가장 큰 요소가 오도록 재배열 시킨다. heap을 사용하면 데이터를 정렬된 순서대로 출력하는데 O(n log n) 만큼 소요되므로 아주 효율적인 알고리즘이다.
다음은 Heap sort 알고리즘을 C언어로 코딩한 것이다.


맺음말
지금까지 기술한 정렬 알고리즘들의 특징을 표로 요약하면 아래와 같다.

정 렬은 입력 자료의 특성과 개수(n)에 따라서 동작하는 효율이 달라 지므로, 입력 자료의 개수 n이 적다면 구현하기 간단한 Insertion sort를 사용하는 것이 바람직하다. 그러나 n의 수가 수 만개 이상으로 많다면 Merge sort나 Quick sort, Heap sort 등을 사용한다. 이때, 기억장소에 대한 부담을 줄이고자 한다면 Quick sort가 바람직하지만, Quick sort는 파티션 하는 과정에서 드물게 비효율성이 발생할 수 있으므로 Heap sort를 사용하는 것이 좀더 좋은 선택이 될 수 있다.  Heap은 정렬을 위해서 유지 관리하는 배열이며 이것을 좀더 응용하면 다음 연재에서 기술하는 다양한 자료구조로 발전 시킬 수 있다. 다음 연재에서는 좀더 다양한 자료구조와 알고리즘에 대해서 기술할 예정이니 독자 여러분들의 꾸준한 관심 바란다.


필 / 자 / 소 / 개

(정 재준) 필자는 학창시절 마이크로프로세서 제어 기술을 배웠고, 10여년동안 쌓아온 IT관련 개발 경험을 바탕으로 “오라클실무활용SQL튜닝(혜지원)” 책을 집필하고, “월간임베디드월드” 잡지에 다수의 글을 기고하였다.  서울대병원 전산실에서 데이터베이스 관련 일을 하면서 학창시절부터 꾸준히 해온 리눅스 연구도 계속하고 있다.  특히, 스탠포드대학교의 John L. Hennessy 교수의 저서 “Computer Organization and Design” 책을 읽고 깊은 감명을 받았으며, 컴퓨터구조와 자료구조 및 알고리즘 효율성 연구를 통한 기술서적 집필에 노력하고 있다.  또한, 온라인 상에서 커널연구회 (http://www.kernel.bz/ )라는 웹사이트를 운영하며 관련기술들을 공유하고 있다.


※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ
Techworld, Inc. 무단전재 및 재배포 금지



맨 위로
맨 위로