제 5 장 트리 (Ⅰ)

◁ 학습 내용 ▷

◦ 트리의 정의 및 표현

◦ 이진 트리의 개요

◦ 이진트리의 표현, 순회 및 응용

* 트리(tree)의 정의

트리는 다음 성질을 만족하는 한 개 이상의 노드를 갖는 유한

집합 T이다.

① T의 원소 가운데 루트 노드라고 하는 특정한 한 개의 노드가

존재하고,

② 루트를 제외한 나머지 노드들은 n개의(n≥0)의 서로 분리된

부분 집합 T1, T2, T3, …, Tn으로 나누어지며, 각 Ti는 트리가

된다. 이때 Ti들은 T의 서브트리(subtree)라 한다.

․용어 : 노드, 루트, 차수, 단말노드, 자식노드, 부모노드, 형제노드,

레벨 노드, 레벨, 트리의 길이, 포리스트, 순서트리, 비순서

트리

*트리의 표현

*순서 트리와 비순서 트리

․순서(ordered) 트리 : 노드의 배열순서가 고정되어, 위치의 의미가

중요한 트리 (이진트리)

․비순서(oriented) 트리 : 노드의 배열 순서에 의미를 부여하지 않는

트리 (일반트리)

위의 그림(a)와 (b)가 일반트리인 경우 같은 트리로 볼 수 있으나, 이진트리일 경우 서로다른 트리이다. 즉 그림(a)의 경우 루트의 왼쪽 자식 노드를 가지는 트리이고, 그림(b)의 경우는 루트에 오른쪽 자식노드를 가지도록 구성된 경우이다.

그림(c)와 (d)는 일반트리로서 좌, 우 위치가 중요한 의미를 갖지 않는 같은 트리이다.

* 이진 트리(binary tree)

[정의] 이진트리는 공집합이거나 한 개의 루트와 좌측 서브트리,

우측 서브트리로 부르는 두 개의 분리된 이진 트리로 구성된 노드

의 유한 집합이다.

* 이진 트리의 레벨과 길이

․보조 정리 5.1 : (i) 이진 트리에서 레벨 i에서의 최대 노드수는

2i-1, i≥1이다.

(ii) 깊이가 k인 이진 트리가 가질 수 있는 최대

노드수는 2k-1, k≥1이다.

증명 : (i) 증명은 i에 대한 귀납법을 이용한다.

귀납 기초 : 레벨 i=1 일 때는 오직 하나의 노드,

즉 루트만이 존재한다. 따라서 레벨  i=1에서의

최대 노드수는 20 = 2i-1이다.

귀납 가설 : 모든 j, 1≤j≤i에 대해서 레벨 j에서

의 최대 노드수는 2j-1이다.

귀납 과정: 위의 가설로부터 I-1에서 최대 노드수

는  2i-2이며, 이진트리에서 모든 노드의 가지수는

최대 차수인 2이므로, 레벨 I에서 최대 노드수는

레벨 I-1에서의 최대 노드수의 2배, 즉 2i-1이다.

(iii) 깊이가 k인 이진 트리에서 가질 수 있는

최대노드수는 [eqn: SUM from { { i}=1} to k] (레벨 i의 최대 노드수)인데,

즉[eqn: SUM from { { i}=1} to k 2^i-1 = 2^k -1]이다.

* 포화 이진 트리와 완전 이진트리

․포화 이진 트리 (full binary tree)

최하위 레벨 I의 노드개수가 2i-1인 이진 트리를 의미한다.

․완전 이진 트리 (complete binary tree)

길이가 k인 어떤 이진 트리의 노드수가 n개일 때, 이 트리의 각

노드들이 루트로부터 시작하여 위에서 아래로 좌측에서 우측으로

각 노드에 붙인 1부터 n까지의 1대 1번호로 대응되는 트리를 의

미한다.

* 보조 정리 5.3

① PARENT(i) I≠1   ⌎i/2⌏

② LCHILD(i) 2*i≤n 2*i

③ RCHILE(I) 2*i+1≤n  2*i+1

이진트리에서 자식노드와 부모노드의 관계는

① PARENT(i) i≠1   ⌎i/2⌏

② LCHILD(i) 2*i≤n 2*i

③ RCHILE(I) 2*i+1≤n  2*i+1

이다. 즉 부모 노드는 i≠1 인 경우, ⌎i/2⌏이며,

i 의 왼쪽 자식노드는 2*i의 위치이며,

i 의 오른쪽 자식노드는 2*i+1의 위치이다.

* 보조 정리 5.2

모든 이진 트리 T에 대해, n0는 단말 노드수, n2는

차수가 2인 노드수라 하면

n0 = n2+1이다.

n = n0+n1+n2

n = 1+n1+2n2

n0 + n1 +n2 = 1+n1+2n2

n0 = n2 +1

* 이진 트리의 표현(배열)

이진트리는 1차원 배열로 표현할 수 있다. 위의 완전 이진트리인 경우, 배열을 빈 공간 없이 활용할 수 있으며, 경사가 진 이진트리의 경우, 4개의 데이터를 저장하기 위해 8개의 공간이 필요하게 된다.

* 이진 트리의 표현(연결리스트)

이진트리의 연결리스트 표현은 왼쪽링크와 오른쪽링크를 나타내기 위한 이중연결리스트에 의해 표현된다. 위의 그림에서 점에 의해 화살표를 연결하는 것은 기억장소의 주소를 기억 상태를 나타낸 것이다.

* 이진 트리의 순회

중위 순회 : LDR

후위 순회 : LRD

전위 순회 : DLR

이진 트리의 순회는 데이터가 찾아지는 순서에 따라 중위순회(왼쪽-데이터-오른쪽), 후위순회(왼쪽-오른쪽-데이터), 후위순회(데이터-왼쪽-오른쪽)의 순회 방법이 있다.

* 중위순회

procedure INORDER(T)

if T ≠ 0 then [call INORDER(LCHILD(T))

print(DATA(T))

call INORDER(CHILD(T))

end INORDER

다음 트리의 중위 순회 과정을 알아본다.

트리를 부분 트리로 나누면 다음과 같다.

중위 순회 과정은 다음과 같다.

(T1          T0          T2)

(T11       T10       T12)         (T21      T20       T22)

(T121       T120        T122)

따라서 중위 순회는 T11 → T10 → T121 → T120 → T122 → T0 →

T21 → T20 → T22,  즉 A/B ** C+D * E가 된다.

* 전위 순회 알고리즘

procedure PREORDER(T)

if T ≠ 0 then [PRINT(DATA(T))

call PREORDER(LCHILD(T))

call PREORDER(RCHILD(T))]

end PREORDER

* 후위 순회 알고리즘

procedure POSTORDER(T)

if T ≠ 0 then [call POSTORDER(LCHILD(T))

call POSTORDER(RCHILD(T))]

PRINT(DATA(T))]

end POSTORDER

*이진 트리에 의한 정렬

data : X, X30, Y, I, K, ZP, DST, A30

INORDER(T) 적용 :

A30, DST, I, K, X, X30, Y, ZP

procedure POSTORDER-EVAL(T)

① if T≠then [call POSTORDER-EVAL(LCHILD(T))

②            call POSTORDER-EVAL(RCHILD(T))

③            case]

④   :DATA(T)='￢':VAL(T) ← not VAL(RCHILD(T))

⑤   :DATA(T)='∨':VAL(T) ← VAL(LCHILD(T)) or

VAL(RCHILD(T))

⑥   :DATA(T)='∧':VAL(T) ← VAL(LCHILD(T))

and VAL(RCHILD(T))

⑦   :else       VAL(T) ← DEF(DATA(T))

⑧      end

end POSTORDER-EVAL

위의 알고리즘은 T라는 이진트리 명제식을 후위순회 방식으로 계산하기 위한 알고리즘이다.

변수 VAL에는 계산결과가 저장된다.

명제식

논리 변수 : x1, x2, x3

연산자 : ∧,∨,￢

x1, x3 : true, x2 : false

( ￢x1∨x2)∧x3 → false

f     f     t

f

명제식 ( ⌍x1∨x2)∧x3 의 이진트리 표현을 오른쪽 트리로 나타낸 것이다.

논리변수x1, x2, x3이 각각  x1, x3 : true, x2 : false 일 때, 식의 계산 결과는

false가 된다.

제 5장 트 리 (Ⅱ)

◁ 학습 내용 ▷

◦ 스레드 이진 트리

◦ 트리의 이진 트리 변환

◦ 히 프

◦ 이진 탐색 트리

◦ 선택트리

◦ 포리스트

◦ 이진트리의 개수계산

* 스레드 이진 트리

스레드 이진트리는 이진트리의 널링크를 이용하여 트리를 순회할 수 있도록 구성한 것이다.

이를 위해 링크 포인터가 정상포인터인가 스레드포인터인가를 식별할 수 있도록 tag비트를

부여하여 표시한다.

스레드 이진트리에서 중위 후속자를 찾는 알고리즘

procedure INSUC(X)

S ← RCHILD(X)

if RBIT(X) = 1 then [while LBIT(S)=1 do

S ← LCHILD(S)

end]

return(S)

end INSUC

위의 if문의 설명 :  x의 RCHILD가 정상포인터이면, x의 우측 자식노드로부터 시작해서

LBIT가 0이 될 때까지 LCHILD를 순회하여, 후속자 S를 찾는다.

스레드 이진트리(T)의 중위순회 알고리즘

procedure TINORDER(T)

HEAD ← T

loop

T ← INSUC(T)

if T = HEAD then return

print(DATA(T))

forever

end TINORDER

위의 알고리즘에서 loop - forever의 실행 내용중 INSUC(T)의 실행은 T가 HEAD노드

이므로 HEAD노드의 후속자를 찾아 return을 하게된다.

그 다음 if문에서 T≠HEAD이므로( T= HEAD인 경우는 순회를 끝낸 상황임) 그 다음

문장으로 내려와 T의 데이터를 프린트한다.

loop - forever의 내용을 반복 실행하다가 T= HEAD인 경우 실행을 종료한다.

* 보조 정리 5.4

n개의 노드를 갖고, 차수가 k인 트리(k-ary tree) T를 k

개의 링크 영역을 갖는 노드 형태로 저장할 때

전체 링크수 = n * k

널링크수 = 전체 - 널이 아닌 링크

= nk - (n-1)

= n(k-1)+1

다양한 차수의 트리 중에서 널 링크의 점유율은 이진트리가 가장 적으며,

따라서 기억공간의 활용에 낭비가 없다.

* 널링크 점유율

[eqn: k = 2, {n+1} over {2n} Image 1 over 2]

[eqn: k = 3, {2n+1} over {3n} Image 2 over 3]

[eqn: k = 4, {3n+1} over {4n} Image 3 over 4]

* 트리의 이진 트리 변환

위의 일반트리를 이진트리로 변환하는 과정은

첫째, 트리의 각 계층에 형제 노드를 연결한다.

둘째, 각노드의 가장 왼쪽 자식노드만 남기고 관계를 단절한다.

셋째, 우측 형제 노드의 관계를 오른쪽 자식 노드의 관계로 설정한다.

이와같이 하여 일반트리를 이진트리로 변환한다.

* 히프(heap)

[정의] 최대 트리(max tree)는 각 노드의 킷값이(자식 노드가

있다면) 그 자식이 킷값보다 작지 않은 트리이다. 최대

히프는 최대트리인 완전 이진 트리이다. 최소 트리(min

tree)는 각 노드의 킷값이(자식이 있다면) 자식이 킷값

보다 크지 않은 트리이다. 최소 히프(min heap)는 최소

트리이면서 완전 이진 트리이다.

위의 완전 이진트리에서 최대 값을 추출하기 위한 과정을 정리하면 다음과 같다.

루트-왼쪽-오른쪽의 관계로 묶어 i=1은 21-16-7, i=2는 16-25-9, i=3은 7-48로 하여

i=3, i=2, i=1의 순서로 루트 값을 계속적으로 갱신하여, 트리에서 가장 큰 값을 루트

로 한다. 이 알고리즘은 교재 298쪽에 제시되었다.

* 이진 탐색 트리(binary search tree)

이진 탐색 트리에서는 삽입, 삭제, 탐색 연산을 지금까지 공부했

던 어떤 자료 구조보다도 더 좋은 성능을 갖는다.

[정의] 이진 탐색 트리는 공백이 가능한 이진 트리이다.

만약 공백이 아니라면 다음 성질을 만족한다.

(1) 모든 원소는 키(key)를 가지며, 어떤 두 원소도 동일한 키를

갖지 않는다. 즉 키는 유일한 값을 가진다.

(2) 공백이 아닌 좌측 서브트리에 있는 키들은 그 서브트리의 루

트의 키보다 작아야 한다.

(3) 공백이 아닌 우측 서브트리에 있는 키들은 그 서브트리의 루

트의 키보다 커야 한다.

(4) 좌측과 우측 서브트리도 이진 탐색 트리이다.

procedure SEARCH(tree, key)

while tree ≠ 0 do

if key = data(tree) then return(tree);

if key < data(tree)

then tree ← LCHILD(tree)

else tree ← RCHILD(tree);

return(NULL)

end

end SEARCH

위의 알고리즘은 이진 탐색트리에서 키 탐색을 위한 알고리즘으로 킷값이 key인

노드를 반환하게된다.

while tree ≠ 0 do 는 트리에 노드가 있는 동안 실행하게되는 구문이며,

if key = data(tree) then return(tree); 는 트리의 데이터와 킷값이 일치하는 경우이고,

그 외의 경우는 다음 조건절에 제시된 if key < data(tree) 에 의해,

then tree ← LCHILD(tree), 그리고 조건을 만족하지 않는 경우는 tree ← RCHILD(tree)

를 실행하게된다. 찾고자하는 노드가 없는 경우는 NULL을 반환한다.

높이가 h인 이진 탐색 트리에 대해 search나 함수를 사용하면

O(h)시간내에 탐색을 수행할 수 있다.

* 이진 탐색 트리에 삽입

* 이진 탐색 트리에서 삭제

* 선택 트리(selection tree)

하나의 정렬된 파일을 만들기 위한 k개의 정렬된 부분 파일(런:run)

이 있다. k개의 런에 있는 레코드의 총수가 n이라면 합병 작업은 가

장 작은 키의 레코드를 반복해서 출력하는 것이 된다. 이를 위해서는

k개의 런 중 가장 작은 레코드를 포함하는 런을 선택하고. 이 런의

첫번째 레코드를 출력해야 할 것이다. k개의 런을 합병하는 가장 직

접적인 방법은 다음에 출력할 레코드를 결정하기 위해 k-1번 비교하

는 것이다. 그러나 선택트리를 이용하며, k개의 런에서 다음번으로 가

장 작은 레코드를 발견하는데 필요한 비교횟수를 줄일 수 있다. 여기서

선택 트리는 각 노드가 두 개의 자식 노드 중에서 더 작은 노드로 표

현하는 이진 트리이며, 루트는 가장 작은 값이 된다. 트리의 레벨수는

⌌log2k⌍ + 1이 되고, 따라서 트리를 재구성하는데 시간은 0(log2k)가

된다. 트리는 레코드가 출력 파일에 합병될 때마다  재구성되어야 하므

로 n개의 레코드를 모두 합병하는데  필요한  시간은 O(n log2k)이다.

처음에 선택 트리를 설정하는데  필요한 시간은 O(k)이므로 k개의 런을

합병하는 전체 시간은 O(n log2k)이다.

각 각의 서브화일(run)에서 가장 작은 값을 추출하고, 두 개의 서브화일 값중

작은 값을 부모 노드로 구성하는 방식으로 가장 작은 값을 루트로 만들어 추출

한다.

선택트리에서 하나의 노드가 추출되고 나서 재구성된 모습을 나타낸 그림으로

화살표 부분은 갱신된 부분을 나타낸 것이다.

위의 선택트리는 토너먼트의 승자, 패자 개념을 이용하여, 최소값을 추출한

예이다. 서브화일에서 추출한 노드군에서 부모를 패자 값으로하고, 그 위의 레벨은

승자 중의 패자, . . . . 이러한 방식으로 트리를 구성하게되면 궁극적으로 최종 승자

가 추출된다.

*포리스트(forest)

[정의] 포리스트[forest]는 n(≥0)개의 분리(disjoint)트리들의

집합이다.

* 포리스트의 이진 트리 변환

[정의] T1, T2, …, Tn의 트리들로 이루어진 포리스트가 있다면

이 포리스트에  대응하는 이진 트리는 B(T1, T2, …, Tn)

으로 표시되며,

(1) n = 0 이면 B는 공백이다.

(2) B는 T1과 같은 루트를 가지며, 좌측 서브트리로 B(T11,

T12, …, T1m)를 가진다[단, T11, T12, …, T1m은 T1

(루트)의 서브트리들이다]. 그리고 우측 서브트리는

B(T2, …, Tn)이다.

* 포리스트의 순회

[전위 순회]

① F가 공백이면 귀환한다.

② F의 첫 트리의 루트를 방문한다.

③ 첫 트리의 서브트리들은  트리 전위로 순회한다.

④ F의 남은 트리들을 전위로 순회한다.

[중위 순회]

① F가 공백이면 귀환한다.

② F의 첫 트리의 서브트리를 트리 중위로 순회한다.

③ 첫 트리의 루트를 방문한다.

④ 나머지 트리를 중위로 순회한다.

[후위 순회]

① F가 공백이면 귀환한다.

② F의 첫번째 트리의  서브트리를 트리 후위로 순회한다.

③ 나머지 트리를 후위로 순회한다.

④ F의 첫 번째 트리의 루트를 방문한다.

* 서로 다른 이진 트리

이진트리는 좌,우 순서가 의미를 가지므로, 이진트리에서 노드가 2인 경우,

트리의 종류는 2개가되고, 노드가 3인 경우, 위의 그림과 같이 서로 다른 트리의

갯수는 5개가된다.

*스택 순열

이진 트리의 전위 및 중위 순회는 다음과 같다.

제 6장 그래프 (Ⅰ)

◁ 학습 내용 ▷

◦ 그래프의 정의

◦ 그래프의 표현

◦ 그래프의 순회

◦ 최소비용신장트리

*그래프의 정의

그래프 G는 정점들의 집합이라 불리는 비공집한 V와 간선들의 집합

E, 간선E에서 정점 V의 쌍으로의 사상으로 구성된다. 여기서 그래프의

두 집합 정점과 간선은 유한하다고 가정하며, G = (V,E)로 표기한다.

*그래프

G = (V,E)

G(b) = (V,E)

V(b) = {[eqn: V_1``,``V_2`] }

E(b) = { <[eqn: V_1 ``,`` V_2] >}

G(c) = (V,E)

V(c) = {[eqn: V_1``,``V_2``] }

E(c) = {([eqn: V_1``,``V_2``] )}

․무방향 그래프 : 간선을 나타내는 정점의 쌍에 순서가 없다.

따라서 ([eqn: V_1`,`V_2`] )와 ([eqn: V_2`,`V_1`] )은 같은 간선임을

나타낸다.

․방향 그래프   : 각 간선이 방향을 가진 정점의 쌍으로 나타낸다.

간선 <[eqn: V_1`,`V_2`] >에서 [eqn: V_1`]은 꼬리(tail)이고, [eqn: V_2`]는

머리(head)이다.   따라서 <[eqn: V_1`,`V_2`] >와 <[eqn: V_2`,`V_1`] >

은 같은 간선이 아니다.

그래프의 간선 [eqn: X` IN `E`]이고, 정점의 쌍([eqn: u`,`v`] )에 관련되면, 간선 [eqn: x`]는

정점[eqn: u`]와 [eqn: v`]에 연결(connect)되었다고 하며, 이때 간선에 의해

연결된 두 정점을 인접(adjacent)되었다고 한다.

위의 그림에서 (b), (e), (g)는 방향 그래프, (c), (f)는 무방향 그래프,

(d)는 혼합 그래프, (a)는 방향 그래프나 무방향 그래프로 고려될 수 있다.

*그래프의 유형 1

무방향 그래프       방향 그래프       혼합그래프

*그래프의 유형 2

다중 그래프              가중 그래프

*그래프의 차수(degree)

정점 1

진입 차수 : 0

진출 차수 : 2

전체 차수 : 2

정점 2

진입 차수 : 3

진출 차수 : 2

전체 차수 : 5

*경로(path)

②에서 ④까지의 경로

[eqn: P_1`=``(2`,`4)`]

[eqn: P_2`=`(2`,3`)``,``(3`,`4`)`]

[eqn: P_3``=``(2`,`3`)`,`(3`,`2)`,(2`,`4)`]

[eqn: P_4`=`(2`,`2)`,`(2,`4)`]

경로(path)는 초기 정점에서 단말 정점에 이르는 간선들의 열을 의미함.

또한 경로상의 간선들의 수를 그 경로의 길이(length)라 함.

*사이클(cycle)

[eqn: C_1`=`(2`,2`)`]

[eqn: C_2`=`(2`,`3)`,(3`,`2)`]

[eqn: C_3`=`(1`,`2)`,`(2`,`4)`,`(4`,`1)`]

[eqn: C_4`=`(1`,`2)`,`(2`,`3)`,`(3`,`4)`,`(4`,`1)`]

같은 정점에서 시작하고 끝나는 경로를 사이클이라 함.

*그래프의 표현(인접 행렬)

[eqn: a_ij``= LEFT { 1`,`<V_i`,`V_j > `IN `E`# 0`,` 그``` 외의 ```경우]

1  2  3

[eqn: MATRIX { { 1}# {2 }# {3}} BMATRIX { { 0}& {1 }& {1 }# { 0}& { 0}& { 1}# { 1}& {0 }& {0 } }]

그래프의 행렬 표현(인접행렬) - 이차원 배열 표현

위의 좌측 그림을 기억공간 상에 나타내기 위한 표현으로 배열에 의한 표현

방법은 오른쪽 표와 같다. 여기에서는 정점이 4이므로 4행 x 4열로 구성되고,

행은 진출방향을 열의 방향은 진입방향을 나타내어 행렬을 구성한다.

[eqn: {{a}_{ij}}^{(2) } = SUM from { { k}=1} to n a_{ij}․a_{kj}]

aij(2)는 i에서 j로 가는 모든 것 중에서 다른 하나의 노드 k를

거쳐 가는 것을 나타낸다.

aij(3)는 i에서 j로 가는 모든 것 중에서 다른 2개의 중간 노드를

거쳐가는 것이다.

* 경로의 개수

* 경로 행렬

그래프의 연결리스트 표현(인접리스트)

*인접 리스트(방향 그래프)

1  A ∙    B ∙    C ∙    D 0

2  B ∙    A ∙    C  0

3  C ∙    D 0

4  D 0

그래프를 기억장치에 나타내기 위한 표현으로 연결리스트를 이용하는 방법은

위의 그래프의 오른쪽과 같은 방법으로 표현한다.

*인접 리스트(무방향 그래프)

1 ∙    2 ∙    3 ∙    4  0

2 ∙    1 ∙    3  ∙   4  0

3 ∙    1 ∙    2 ∙    4  0

4 ∙    1 ∙    2 ∙    3  0

*그래프의 순회

․깊이 우선 탐색(depth first search)

시작 정점 V를 기점으로 하여, V에 인접하면서 방문하지 않은 정점

W를 택하고 W를 시작점으로 하여 깊이 우선 탐색을 다시 시작한다.

방문한 어떤 점정으로 부터 방문되지 않은 정점에 도달할 수 없을 때

탐색이 끝난다.

․너비 우선 탐색(breadth first search)

정점 V에서 시작하여 V를 방문한 것으로 표시한 후, V에 인접한

모든 정점(형체 노드 방향)들을 방문한다.

(a)

1 [eqn: V_1`]∙    2 ∙    3 ∙    4

2 [eqn: V_2`]∙    1 ∙    5 ∙    6

3 [eqn: V_3`]∙    1 ∙    6

4 [eqn: V_4`]∙    1 ∙    6 ∙    7

5 [eqn: V_5`]∙    2 ∙    8

6 [eqn: V_6`]∙    2 ∙    3 ∙    4 ∙    8 ∙   9

7 [eqn: V_7`]∙    4 ∙    9

8 [eqn: V_8`]∙    5 ∙    6 ∙    9

9 [eqn: V_9`]∙    6 ∙    7 ∙    8

(b)

procedure DFS([eqn: v`])

VISITED([eqn: v`])[eqn: <- `1`]

for [eqn: v`]에 인접한 각 장점 [eqn: w`]에 대하여 do

if VISITED([eqn: w`]) = 0 then call DFS([eqn: w`])

end

end DFS

인접 행렬로 G를 나타낼 때 [eqn: v`]에 인접한 모든 정점을 결정하는 데는

[eqn: 0(n)`]의 시간이 걸린다.   방문해야 할 정점의 수는 [eqn: n`]을 넘지 않으므로

총시간은 [eqn: 0(n^2`)`]이다.

procedure BFS([eqn: v`])

VISITED([eqn: v`])[eqn: <- `1`]

Q를 비운다.

loop

for [eqn: v`]에 인접한 모든 정점 [eqn: w`]에 대하여 do

if VISITED([eqn: w]) = 0

then [call ADDQ([eqn: w`,`]Q) ;

VISITED([eqn: w])[eqn: <- `1`]]

end

if Q가 비어 있으면 then return

call DELETEQ([eqn: v`,``]Q)

forever

end BFS

인접 행렬이 사용될 경우 for 루프는 방문되는 각 정점에 대해서

[eqn: 0(n)`]의 시간이 걸린다.   따라서 총 [eqn: 0 (n^2 )`]의 시간이 걸린다.

*신장 트리

완전 그래프                  신장 트리

․완전 그래프가 되기 위한 조건

정점의 개수가 [eqn: n`]일 때 간선의 수는

[eqn: n(n`-`1)/2`]이다.

정점이 3개 : 3

〃   4개 : 6

〃   5개 : 10

*최소 비용 신장 트리

Prim 방법

현재 T에 포함된 간선들이 정점과 연결된 간선 중에서 최소 비용

간선을 선택하는 방법이다.

Kruskal 방법

간선들을 하나씩 결정하여 마지막으로 최소 비용 신장트리 T를

만들게 된다.  간선들은 그 비용이 적은 순으로 T에 포함하게 되는데,

각 간선은 이미 T 속에 있는 간선들과 비교해서 사이클을 형성하지

않으면 그 간선은 T에 포함시키는 방법이다.

*샘플 그래프

procedure PRIM

① T[eqn: `` <- ``PHI `]

② W[eqn: <- `` PHI ``]

③ choose an edge([eqn: v`,`w`]) from E of lowest cost

④ while T contains less than [eqn: n-1`] edges and E not

empty do

⑤  delete([eqn: v`,w``]) form E

⑥ if([eqn: v`,w`]) does not create a cycle in T

⑦   then

⑧	add([eqn: v`,`w`]) to T

⑨      W[eqn: <-]W[eqn: BIGCUP LEFT{v`,`w`right}`]

⑩	else

⑪	discard([eqn: v`,`w`])

⑫    choose an edge([eqn: v`,`w`]) from E of lowest

cost connected

⑬	to one of he vertex in [eqn: w`]

⑭ end

end PRIM

․Prim 알고리즘의 실행 단계

간선         비용        정점([eqn: w`])       신장 트리(T)

(1 , 2)        10          {1 , 2}         ①         ②

(2 , 6)        25        {1 , 2 , 6}        ①         ②

⑥

(3 , 6)        15      {1 , 2 , 3 , 6}      ①          ②

⑥          ③

(6 , 4)        20    {1 , 2 , 3 , 4 , 6}       ①        ②

④           ③

⑥

(1 , 4)       거부

(3 , 5)        35    {1 , 2 , 3 , 4 , 5 , 6}  ①         ②

⑤

④            ③

⑥

․Kruskal 알고리즘의 실행 단계

간  선           비  용           신장 포리스트(forest)

①   ②  ③  ④  ⑤  ⑥

(1 , 2)             10            ①   ②  ③  ④  ⑤  ⑥

(3 , 6)	15            ①   ②  ③  ④  ⑤

⑥

(4 , 6)             20            ①   ②      ③  ⑤

④   ⑥

(2 , 6)             25            ①   ②           ⑤

④        ③

⑥

(1 , 4)             30                       거부

①   ②

⑤   ③

④

⑥

procedure KRUSKAL

① while T contains less than [eqn: n-1`] edges and E not

empty do

choose an edge([eqn: v`,`w`]) from E of lowest cost;

②     delete ([eqn: v`,`w`]) from E:

③ if([eqn: v`,`w`]) does not create a cycle in T

④   then add ([eqn: v`,`w`]) to T

⑤  else discard ([eqn: v`,`w`])

⑥ end

end KRUSKAL

제 6 장 그래프 (Ⅱ)

◁ 학습 내용 ▷

◦ 주경로(critical path)

◦ 최단 경로(shortest path)

◦ 순차탐색, 이진탐색, 피보나치 탐색

◦ 정렬의 개요

*최조 완료 시간(TE)

( 각 정점에서 한 활동이 시작되기 전에 그것에 의존하는 모든

활동이 완료되는 시간)

[eqn: TE(V_1 )`=`0`]

[eqn: TE(V_j`)`=`max`left{`t(p)`right}``,``j`not=`1`]

․최조 완료 시간(earliest completion time : TE)

아래의 그래프에서 각 정점의 TE값이 최조 완료시간이 된다.

*최종 완료 시간(TL)

( 각 정점에서 최조 완료시간에 더 이상 연기를 증가하지 않고,

한 활동을 완료할 수 있는 가장 늦은 시간)

[eqn: TL(V_n )`=`TE(V_n )`]

[eqn: TL(V_j )`=`TE(V_n ) - max left{t(p) right}`,`j `not= `n`]

․최종 완료 시간 (latest completion time : TL)

아래의 그래프에서 각 정점의 TL값이 최종 완료시간이 된다.

최조완료시간(TE)와 최종완료시간(TL)이 일치하는 정점이 주경로가 된다.

[eqn: V_1`-`V_3`-`V_4`-V_6`]

․알고리즘 CREATE

포괄적인 배열 구조들인 DATA, TE, TL, POINTER, TIME, DEST가

주어졌을 때, 이 알고리즘은 PERT 그래프에 존재하는 관계들을 반영하기

위해 입력 화일로부터 간선 데이터를 읽고, 이런 배열들의 원소들에 값을

할당한다. 변수 NO-NODES와 NO-EDGES는 포괄적인 것으로 간주되며,

그래프상에서 만나는 각각 다른 장점들의 수와 다른 간선들의 수를 나타낸다.

procedure GREATE

①  //초기화//

TE[eqn: <- `]POINTER[eqn: <- `]0

DATA[eqn: <- `] '   '

NO-NODES [eqn: <- `]NO-EDGES [eqn: <- `]0

TL[eqn: <- `][eqn: INF `]

② //데이터 항목들의 첫 번째 집합을 읽음//

read(ORIGIN, INFO, WEIGHT, END)

③ //더 이상의 데이터가 없을 때까지 처리의 계속//

for EOF encountered do

④ //배열 원소들의 값을 할당//

if ORIGIN<NO-NODES

then write('DATA OUT OF SEQUENCE')return

if INFO[eqn: NOT=`]'  '

then DATA(ORIGIN)[eqn: <- `]INFO

if ORIGIN>NO-NODES

then //새로운 노드//

NO-NODES[eqn: <- `]NO-EDGES+1

POINTER(NO-NODES)[eqn: <- `]NO-EDGES+1

if END[eqn: <=`]0

then return

else NO-EDGES[eqn: <- `]NO-EDGES+1

TIME(NO-EDGES)[eqn: <- `]WEIGHT

DEST(NO-EDGES)[eqn: <- `]END

else   //같은 노드//

if   END[eqn: <=`]0

then write('NONSINK NODE HAS AN EDGE

WITH INVALID DESTINATION')

return

else NO-NODES[eqn: <- `]NO-EDGES+1

TIME(NO-EDGES)[eqn: <- `]WEIGHT

⑤ //다음 입력 데이터의 읽음//

read(ORIGIN, INGO, WEIGHT, END)

⑥ end

end CREATE

․알고리즘 PROCESS

이전에 기술된 것과 같이 NO-NODES와 NO-EDGES와 함께 포괄

적인 배열들이 주어졌을 때, 이 알고리즘은 각 정점에 대한 TE와 TL

을 계산하고 저장한 뒤 주경로상에 있는 정점들을 출력시킨다. NODE

#와 EDGE#는 어떤 정점과 어떤 간선이 현재 조사중인지를 나타낸다.

procedure PROCESS

① // TE 값을 계산하기 위한 초기화//

NODE#[eqn: <- `]1

EDGE#[eqn: <- `]POINTER[1]

② //각 노드에 대한 TE값의 계산//

while NODE#<NO-NODES do

while EDGE#<POINTER[NODE#+1] do

TE[DEST[EDGE#]][eqn: <- `]max{TE[DEST[EDGE#]],

TE[NODE#]+TIME[EDGE#]}

EDGE#[eqn: <- `]EDGE#+1

NODE#[eqn: <- `]NODE#+1

end

end

③ //TL값을 계산하기 위한 초기화//

TL[NODE#][eqn: <- `]TE[NODE#]

NODE#[eqn: <- `]NO-NODES-1

EDGE#[eqn: <- `]NO-EDGES

④ //각 노드에 대한 TL값의 계산//

while EDGE#[eqn: <=`]1 do

while EDGE#[eqn: >=`]POINTER[NODE#] do

TL[NODE#][eqn: <- `]min{TL[NODE#],

TL[DEST[EDGE#]]-TIME[EDGE#]}

EDGE#[eqn: <- `]EDGE-1

end

end

⑤ //주 경로상에 노드를 출력//

for NODE# = 1 to NO-NODES do

if  TE[NODE#] = TL[NODE#]

then write(NODE#, DATA[NODE#])

end

end PROCESS

*최단 경로

출발점   종착점   최단길

1        1         0

1        2        20

1        3        25

1        4        45

1        5        50

출발점     종착점

1          3             1-2-3(25)

1-3  (30)

1          4             1-2-4  (60)

1-3-4  (50)

1-2-3-4(45)

1          5             1-2-3-4-5(50)

1-2-3-5  (55)

1-2-4-5  (65)

1-3-5    (60)

1-3-4-5  (55)

procedure SHORTEST-PATH([eqn: v``], COST, DIST,[eqn: n`] )

① declare [eqn: S`(`l`:`n`)`]

②  for [eqn: i` <- `1`] to [eqn: n`] do

③    [eqn: S(i)` <- `0``]; DIST([eqn: i`])[eqn: <- `]COST([eqn: v`,i`])

④  end

⑤  [eqn: S(v)` <- 1``]; DIST([eqn: v`])[eqn: <- `]0 ; [eqn: n u m` <- `2``]

⑥  while [eqn: n u m `<`n`] do

⑦   [eqn: c h o o s e```u`] ; DIST([eqn: u`]) =[eqn: min]{DIST([eqn: w`])}

⑧    [eqn: S(u) <- 1``] ; [eqn: n u m` <- `n u m `+`1`]

⑨    for  [eqn: all``w``with``S(w)``=``0`] do

⑩     DIST([eqn: w`])[eqn: <- `][eqn: min]{DIST([eqn: w]),DIST([eqn: u] )

+COST([eqn: u`,`w`] )}

⑪     end

⑫  end

end SHORTEST-PATH

이 알고리즘은 while 루프가 [eqn: n^2`]번 수행하므로 전체 수행시간은

[eqn: 0`(n^2 )`]이 된다.

*모든 쌍의 최단 경로

[eqn: i`not=`j`] 인 모든 정점들의 쌍 [eqn: v_i``,``v_j``] 사이의 최단 경로를 찾는 것을

말한다. 그래프 G는 COST([eqn: i``,``j``]) = 0 이고, [eqn: i`not=`j`] 일 때 간선 <i, j>

로 표시되는 비용 인접 행렬로 표현된다.

[eqn: A^k (i, j) = min`left{A^k-1 (i, j) , A^k-1 (i, k), A^k-1 (k, j)}, k>=1]

[eqn: A^0`(i`,`j)``=``]COST(i, j)

[eqn: A^n`(`i`,`j`)`]를 계산하는 알고리즘이 ALL-COSTS이다.

1      2      3

1    0      4      11

2    6      0      2

3    3     [eqn: INF]     0

(a) 그래프 G         (b) G에 대한 비용 행렬

procedure ALL-COSTS(COST, A, [eqn: n`])

① for [eqn: i` <- `1``]to [eqn: n`] do

②   for [eqn: j` <- `1``] to [eqn: n``] do

③    [eqn: A`(`i`,`j`)` <- ``]COST([eqn: i`,`j] )

④    end

⑤ end

⑥ for [eqn: k` <- `1`] to [eqn: n`] do

⑦    for [eqn: `i` <- `1`] to [eqn: n`] do

⑧     for [eqn: j` <- `1`] to [eqn: n`] do

⑨      [eqn: A(`i`,`j)` <- `min`{`A`(i`,`j`)`,`A`(`i`,`k`)`+`A`(`k`,`j`)`}``]

⑩     end

⑪   end

⑫ end

end ALL-COSTS

*ALL-COSTS에 의해 생성된 행렬

[eqn: A ^(0)``]   1     2     3               [eqn: A^(1)`]   1     2     3

1     0     4    11                 1     0     4     11

2     6     0     2                 2     6     0     2

3     3    [eqn: INF]    0                 3     3     7     0

[eqn: A^(1)`]에서 (3,2)가 7로 바뀐 것은 V1을 거쳐갈 경우 7(3+4)로 변경된다.

[eqn: A^(2)`]   1     2     3               [eqn: A^(3)`]   1      2     3

1     0     4     6                 1    0      4     6

2     6     0     2                 2    5      0     2

3     3     7     0                 3    3      7     0

[eqn: A^(2)`]에서 (1,3)이 6으로 바뀐 것은 V2를 거칠 경우 6(4+2)이고,

[eqn: A^(3)`]에서 (2,1)의 5는 V3을 거친 경우 5(2+3)에 의한 결과이다.

*이행적 폐쇄

A가 G의 인접 행렬일 때, 만약 길이가 양인 경로에서 [eqn: i`]에서 [eqn: j``]로

가는 경로가 존재하면 [eqn: A^+`(`i`, `j `)`=``1``]  이고, 그렇지 않으면 0이 되는

성질을 갖는 행렬 [eqn: A^+`]를 G의 이행적 폐쇄 행렬이라 부른다.

그리고 [eqn: i`]에서 [eqn: j`]로 가는 길이 0보다 크거나 같은 경로가 존재하면,

[eqn: A^* ``(`i`,`j`)`=`1``]이고, 그렇지 않으면 0인 특성을 갖는 행렬 [eqn: A^*``]를 G의 반사

이행적 폐쇄 행렬이라 한다.

1  2  3  4  5

[eqn: MATRIX { 1#2#3#4#5}BMATRIX { { 0}& {1 }& {0 }&{0}&{0}# {0 }& {0 }& {1 }&{0}&{0}# {0}&{0}&{0}&{1}&{0}# {0}& {0}& {0}&{0}&{1}#{0}&{0}&{1}&{0}&{0}}]

(a) 방향 그래프 G                (b) G에 대한 인접 행렬 A

1  2  3  4  5                        1  2  3  4  5

[eqn: MATRIX { {1 }# {2 }# {3 }#{4}#{5} } BMATRIX { { 0}& {1 }& {1 }&{1}&{1}# { 0}& {0 }& {1 }&{1}&{1}# { 0}& {0 }& {1 }&{1}&{1}#{0}&{0}&{1}&{1}&{1}#{0}&{0}&{1}&{1}&{1}}``]                    [eqn: MATRIX { { 1}# {2 }# {3 } #{4}#{5}} BMATRIX { { 1}& {1 }& {1 }&{1}&{1}# { 0}& {1 }& {1 }&{1}&{1}# {0 }& {0 }& {1 }&{1}&{1}# {0}&{0}&{1}&{1}&{1}#{0}&{0}&{1}&{1}&{1} }`]

(c)[eqn: A^+`]                                (d)[eqn: A^*`]

*탐색(search)

기억 공간에 보관된 자료들 중에서 어떤 성질을 만족하는 자료를

찾아내는 것

<탐색을 위한 전제>

․탐색의 대상인 자료를 적절한 구조로 기억 공간에 표현

․표현된 자료들 중에서 원하는 것을 찾는 적절한 방법 선택

*순차 탐색

․순차적으로 편성된 화일에 대한 검색

처음부터 원하는 자료를 찾을 때까지 하나씩 비교(정렬되지 않는

화일에 적합)

[eqn: SUM from { {i }=1} to n``(n`-`i`+1`)`/`n`=`(n`+`1`)`/`2`]

procedure SEQSRCH[eqn: (F`,`n`,`i`,K)`]

[eqn: K_0` <- `K`;`i` <- `n`]

while [eqn: K_i`not=`K`]  do

[eqn: i` <- `i`-1`]

end

end SEQSRCH

* 이진 탐색(binary search)

․정렬된 화일 사용

․탐색 대상을 전체 자료의 중앙값을 비교하며, 반씩 압축

①[eqn: K`<`K_m`]이고 찾고자 하는 레코드가 이 화일에 있다면, 그것은

이 화일에서 키값이 [eqn: K_m`]  보다 작은 화일의 반쪽부분에 있을

것이다.

②[eqn: K>K_m`]이고 찾고자 하는 레코드가 이 화일에 있다면 그것은 이

화일의 키값이[eqn: K_m`] 보다 큰 화일의 반쪽 부분에 있을 것이다.

․탐색 시간은 [eqn: 0(log_2` n)`]이다.

procedure BINSRCH[eqn: (F`,`n`,`i`,`K)`]

① [eqn: l` <- `1`;`u` <- `n``]

② while [eqn: l`<=`u`] do

③   [eqn: m` <- `⌊`(l+u)/2⌋`]

④  case

⑤     : [eqn: K`>`K_m``:` l` <- `m+1`]

⑥     : [eqn: K`=`K_m``:`i` <- `m`;``]  return

⑦     : [eqn: K`<`K_M``:`u` <- `m`-1`]

⑧    end

⑨  end

⑩  [eqn: i` <- `0`]

end BINSRCH

1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

7  19  26  29  33  42  48  53  65  68  72  78  82  89  92

89   1 + 15 = ⌊16/2⌋ =  8      53

9 + 15 = ⌊24/2⌋ = 12      78

13 + 15 = ⌊28/2⌋ = 14      89

*피보나치 탐색

․피보나치 수열에 따라 서브화일로 나누어 탐색

․[eqn: F_0``=``0`,`F_1``=``1`,`F_i``=``F_i-1`,`+`F_i-2``]

․평균 연산 효율 양호(나눗셈을 사용하지 않고, 덧셈과 뺄셈만으로 사용)

[eqn: n`=`F_k `-1`] 이라고 가정하고 피보나치 탐색이 어떻게 수행되는가를

알아본다.

키 [eqn: K`]의 첫 번째 비교는 [eqn: K_F_k-1`]과 이루어지며 그 결과는 다음과 같다.

① [eqn: K<K_F_k-1`]인 경우에는 1부터 [eqn: F_k-1 `-`1`] 까지의 서브화일이 탐색되어야

하며, 이 화일의 크기는 피보나치 수보다 하나 작다.

② [eqn: K`=`K_F_k-1`]이라면 탐색은 성공적으로 끝난다.

③ [eqn: K`>`K_F_k-1`]인 경우에는 [eqn: F_k-1`+`1`] 부터 [eqn: F_k-1`]까지의 서브화일이 탐색

되어야 하며, 이 화일의 크기는[eqn: F_k `-`1`-`(F_k-1`+`1`)`+`1`=`F_k`-]

[eqn: 1`=`F_k-2`-1`]이  된다.

n = 20인 경우

procedure FIBSRCH[eqn: (G`,`n`,`i`n`K)`]

① [eqn: i` <- `F_k-1``;``p` <- `F_k-2``;``q` <- `F_k-3``]

② if [eqn: K>K_i`] then [eqn: [`i` <- `i+m`]`]

③ while [eqn: i`not=`0`] do

④   case

⑤      : [eqn: K`<`K_i`] : if [eqn: q`=`0`] then [eqn: i` <- `0`]

else [eqn: [i` <- `i`-`q:t` <- `t` <- `p`:`p` <- `q`:`q` <- t`-`q]`]

⑥      : [eqn: K`=`K_i`]  : return

⑦      : [eqn: K`>`K_i``] : if [eqn: p`=`1`] then [eqn: i` <- `0`]

else [eqn: [`i` <- `i`+`q``:` p` <- `p`-`q``;``q` <- `q`-p`]`]

⑧    end

⑨ end

end FIBSRCH

1  2  3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20

5  8  9  14  20  22  25  28  36  49  51  53  55  59  62  64  69  72  83  92

*정렬(sorting)

정렬은 정렬을 수행하게 되는 기억 공간에 따라 내부 기억장소냐,

외부 기억장소냐에 따라, 내부 정렬(주기억 장치에서 이루어지는 정렬)

과 외부 정렬(보조 기억장치에서 이루어지는 정렬)로 구분하여 설명할

수 있다.

본 교재에서는 내부 정렬에 관해 다루고 외부 정렬에 관해서는 다음

*내부 정렬 기법의 분류

․삽입법 : 삽입 정렬, 쉘 정렬

․교환법 : 퀵 정렬, 버블 정렬

․합병법 : 2원 합병 정렬

․선택법 : 히프 정렬, 선택 정렬

․분배법 : 기수 정렬

학기의 화일 처리에서 다룬다.

*정렬 알고리즘의 특성

알고리즘	성 능		필요 공간
	평 균	최 악
삽입 정렬 쉘 정렬 퀵 정렬 버블 정렬 합병 정렬 히프 정렬 선택 정렬 기수 정렬	[eqn: 0`(n^2`)`] [eqn: 0`(`n root n`)`][eqn: 0`(n`log n`)`] [eqn: 0`(n^2`)`] [eqn: 0`(n log n`)`] [eqn: 0`(n log n`)`] [eqn: 0`(n^2`)`] [eqn: 0`(d`(`n+r)`)`]	[eqn: 0`(n^2`)`] [eqn: 0`(n`(log n`)^2`)`] [eqn: 0`(n^2`)`] [eqn: 0`(n^2`)`] [eqn: 0`(n log n`)`] [eqn: 0`(n log n`)`] [eqn: 0`(n^2`)`] [eqn: 0`(n^2`)`]	[eqn: n``] [eqn: n``] [eqn: n``+`log_2`n``] [eqn: n``] [eqn: 2n``] [eqn: n``] [eqn: n``] [eqn: n``]

제 7 장 정렬 Ⅱ

◁ 학습 내용 ▷

◦ 삽입 정렬, 쉘 정렬

◦ 퀵정렬, 버블정렬

◦ 2원 합병정렬

◦ 히프정렬, 선택정렬

◦ 기수정렬

*삽입정렬 (insertion sort)

․정렬된 순서로 나열된 레코드  [eqn: R_1`,` R_2`,` …`,`R_n`]  에 [eqn: R`]을 삽입

․자료가 소량인 경우 유리하며, 알고리즘이 간단하다.

․평균 연산 시간은 [eqn: 0(n^2`)`]이다.

procedure INSERT[eqn: (R`,`j)`]

[eqn: j` <- `i]

while [eqn: K`<`K_j`] do

end

[eqn: R_j+1` <- `R`]

end INSERT

본 교재 p.39의 2.2. 순서 리스트의 (5)번항 삽입(insert)을 참조하기 바란다.

다음과 같은 화일이 있다고 하자.

1  2  3  4

2   5  7  9

여기서 key값이  6  인 레코드를 삽입한다고 하면,

1  2  3  4  5

2  5  6  7  9

가된다.

procedure INSORT[eqn: (R`,`n`)`]

[eqn: K_0` <- `- INF `]

for [eqn: j` <- `2`] to [eqn: n`] do

[eqn: T` <- `R_j`]

call INSERT[eqn: (T`,`j-1`)`]

end

end INSORT

예) [eqn: n=7`] 이고 입력 화일이 (64, 28, 33, 76, 55, 12, 43)일 때, 오름차순에 의한 삽입 정렬 과정은 다음과 같다.

초기  64  28  33  76  55  12  43

[eqn: i`=`2`] 28  64

[eqn: i`=`3`]  28 33  64

[eqn: i`=`4`]  28  33  64 76

[eqn: i`=`5`]  28  33 55  64  76

[eqn: i`=`6`] 12  28  33  55  64  76

[eqn: i`=`7`]  12  28  33 43  55  64  76

* 쉘 정렬(shell sort)

․입력 화일을 여러 개의 부분 화일로 세분화, 부분 화일을 삽입 정렬 방법에 따라 순차적    으로 정렬

․평균 연산 [eqn: 0`(n^2`)`]

procedure Shellsort[eqn: (R,`n,`h`,t`)`]

① for [eqn: S` <- `t`] to 1 by -1 do

②      [eqn: h` -> `h_s`]

③     for [eqn: i` <- `h+1`] to [eqn: n`] do

④      [eqn: K` <- `R_j`]

⑤       [eqn: j` <- `j`-`h`]

⑥      while [eqn: j`>`0`] and [eqn: R_j`>`K`] do

⑦       [eqn: R_j+h` <- `R_j`]

⑧       [eqn: j` <- `j`-`h``]

⑨      end

⑩       [eqn: R_j+h` <- `K`]

⑪      end

⑫   end

end Shellsort

예) 입력 화일 [eqn: R`=`(70`,`17`,`26`,`69`,`72`,`53`,`31`,`6`,`45`,`11`,`44`,`47`)]과 증분값 [eqn: h`=`(1`,`2`,`3`,`4`,`6`)`]의 값이 주어졌을 때, 쉘 정렬 결과는 다음과 같다.

초기 상태 70, 17, 26, 69, 72, 53, 31, 6, 45, 11, 44, 47

1단계

70  17  26  69  72  53  31  6  45  11  44  47

[eqn: (h_5`=`6)`]

1단계의

31   6  26  11  44  47  70  17  45  69  72  53

결과

2단계

31   6  26  11  44  47  70  17  45  69  72  53

[eqn: (h_4`=`4)`]

3단계

31   6  26  11  44  47  70  17  45  69  72  53

[eqn: (h_3`=`3`)`]

4단계

11   6  26  31  17  45  69  44  47  70  72  53

[eqn: (h_2`=`2`)`]

5단계

11  6  17  31  26  44  47  45  69  53  72  70

[eqn: (`h_1`=`1`)`]

정렬 결과    6  11  17  26  31  44  45  47  53  69  70  72

*퀵 정렬(quick sort)

․현재 처리되는 key값이 전체 화일에서 올바른 위치에 오도록 정렬 수행

․평균 연산 시간 [eqn: 0`(n log`n)`]

procedure QSORT[eqn: (m`,`n)`]

① if [eqn: m<n`]

then [eqn: [`i` <- `m`;`j <- n+1`;`K>=K_m``]

②    loop

③      repeat [eqn: i` <- `i+1`] until [eqn: K_i`>=`K ;`]

④      repeat [eqn: j` <- `j`-1``]until [eqn: K_j`<=`K`;`]

⑤      if  [eqn: i`<`j]

then call INTERCHANGE[eqn: (R(i)`,`R(j))`]

else exit

⑥      forever

⑦      call INTERCHANGE[eqn: (R(m)`,` R(j))`]

⑧      call QSORT[eqn: (m`,`j-1)`]

⑨      call QSORT[eqn: (j+1`,`n)]`]

end   QSORT

예) 키가 각각 (26, 5, 37, 1, 61, 11, 59, 15, 48, 19)인 10개의 레코드를 가진 k나의 화일이 있다.   아래 표는 QSORT 호출될 때마다의 상태를 보여준다.  사각 괄호는 정렬되어야 할 서브화일을 구분하기 위한 것이다.

[eqn: R_1`] [eqn: R_2`] [eqn: R_3`] [eqn: R_4`] [eqn: R_5`] [eqn: R_6`] [eqn: R_7`] [eqn: R_8`] [eqn: R_9`] [eqn: R_10`] [eqn: m`] [eqn: n`]

초기 상태  [26  5   37   1   61   11  59   15  48  19]   1  10

1단계   [11  5   19   1   15]  26  [59   61  48  37]   1  5

2단계   [ 1  5]  11  [19   15]  26  [59   61  48  37]   1  2

3단계     1  5  11  [19   15]  26  [59   61  48  37]   1  2

4단계     1  5  11   15   19  26   [59   61  48  37]   7 10

5단계     1  5  11   15   19  26   37   48  59  [61]   7  8

6단계     1  5  11   15   19  26   37   48  59  [61]  10  10

1  5  11   15   19  26   37   48  59  61

위의 예제에서 초기 상태부터 1단계까지의 과정을 설명하면 다음과 같다.

[eqn: i`=`1`], [eqn: j`=`11`], [eqn: K`=`26`]인 상태부터 loop～forever의 실행내용은,

26  5  37  1  61  11  59  15  48  19

[eqn: i`=`3`], [eqn: j`=`10`], if 3<10 이므로 37과 19를 교환,

26  5  19  1  61  11  59  15  48  37

[eqn: i`=`5`], [eqn: j`=`8`], if 5<8 이므로 61과 15를 교환,

26  5  19  1  15  11  59  61  48  37

이때[eqn: i`=`7`], [eqn: j`=`6`], 이 되므로 loop문을 벗어나 26과 11을 교환한다.

11  5  19  1  15  26  59  61  48  37

*버블 정렬(bubble sort)

․왼쪽에서 오른쪽으로 인접한 두 요소를 반복적으로 비교해가면서 크기 순서로 바뀐 것    을 교환

․평균 연산 시간[eqn: 0`(n^2 )`]

procedure Bublesort[eqn: (X`,`n)`]

① [eqn: k`<- `n`]

② while [eqn: k`not=`0`] do

③       [eqn: t` <- `0`]

④      for [eqn: j`=`1`] to [eqn: k-1`]do

⑤                if [eqn: X_j`>`X_j+1`] then

⑥                          [eqn: X_j` <-> `X_k+1`]

⑦                             [eqn: t` <- `j`]

⑧              [eqn: k` <- `t`]

end Bubblesort

[eqn: X_1`]  [eqn: X_2`] [eqn: X_3`]  [eqn: X_4`]  [eqn: X_5`] [eqn: X_6`] [eqn: X_7`]  [eqn: X_8`]

1단계      4    7    3    1    5    8    2    6

2단계      4    3    1    5    7    2    6    8

3단계      3    1    4    5    2    6    7    8

4단계      1    3    4    2    5    6    7    8

5단계      1    3    2    4    5    6    7    8

6단계      1    2    3    4    5    6    7    8

7단계      1    2    3    4    5    6    7    8

1    2    3    4    5    6    7    8

* 2원 합병 정렬( 2-way merge sort)

․정렬되어 있는 2개의 서브화일을 단계적으로 정렬

․평균 연산 시간 [eqn: 0(n``log`n)`]

procedure MERGE[eqn: (X,`l,`m,`n,`Z)`]

① [eqn: i` <- `k` -> `;``j `<- `m`+`1``]

② while [eqn: i`<=`m`] and [eqn: j`<=`n`] do

③    if [eqn: x_i`<=`x_j``], then [eqn: [`Z_k` <- `;`i` <- `i`+1`]`]

④    [eqn: k` <- `k`+`1`]

⑤ end

⑥ if [eqn: i>m`] then [eqn: (`Z_k`,`…`,`Z_n`)`` <- ``(X_j`,`…`,`X_n`)`]

else [eqn: (`Z_k`,`…`,`Z_n`)` <- `(`X_i`,`…`,`X_n`)`]

end MERGE

․2개의 화일을 merge하기 위한 algorithm

예) 입력 화일이 (26, 5, 77, 61, 11, 59, 15, 48, 19)이다.

다음 트리는 각 단계에서 합병되고 있는 서브화일을 나타내고 있다.

[26]  [ 5]  [77]  [ 1]  [61]  [11]  [59]  [15]  [48]  [19]

[ 5   26]  [1     77]  [11   61]  [15    59]  [19   48]

[ 1    5   26    77]  [11   15    59    61]  [19   48]

[ 1    5   11    15   26   59    61    77]  [19   48]

[ 1    5   11    15   19   26    48    59    61   77]

procedure MPASS[eqn: (X`,`Y`n`,`l`)`]

① [eqn: i` <- `1`]

② while [eqn: i`<=`n`-`2l`+`l`]   do

③  call MERGE [eqn: (X`,`i`+`l`-`1`,`i`+`2l`-`l`,Y`)`]

④   [eqn: i` <- `i`+`2l`]

⑤  end

⑥  if [eqn: i`+`l`-`1`<`n`]  then call MERGE[eqn: (X`,` i`,`i`+`1``-`l`,`n`,Y`)`]

else[eqn: (Y_i `,`…`,`Y_n`)` <- `(X_i`,`…`,`X_n`)`]

end MPASS

③행은 크기가 [eqn: l`]인 인접함 2개의 서브화일을 merge하여 크기가 [eqn: 2l`]인

서브화일을 계소개서 만들어 가는 과정이다.

②행-⑤행의 초기 상태의 실행 내용은 [eqn: i`<=`9`]인 조건 아래 (X, i, i+l-1,

i+2l-1, Y)

1     1          2

3     3          4

5     5          6

7     7          8

9     9         10

그리고 [eqn: i`=`11`] 일 때 루프를 벗어난다.

⑥행은 입력 화일 X의 merge되지 않고 남은 끝 부분이 [eqn: 2l`]보다 작은 경우를 처리하는 과정이다.

procedure MSORT[eqn: (X`,`n)`]

① declare [eqn: X(n)`], [eqn: Y(n)`]

② [eqn: l ` <- `1`]

③ while [eqn: l<n`]do

④   call MPASS[eqn: (X`,`Y`,`n`,` l)`]

⑤    [eqn: l` <- `2`*`l`]

⑥   call MPASS (Y, X, n, l)

⑦    [eqn: l` <- `2`*`l`]

⑧   end

end MSORT

파일의 전체적인 정렬이 한번에 이루어지지 않고, 여러 단계를 거치게 되므로

④ call MPASS[eqn: (X`,`Y`,`n`,` l)`]  에서 X를 입력으로 Y를 만들고,

⑥ call MPASS (Y, X, n, l)에서는 Y를 입력으로 X를 만든다.

*히프 정렬(heap sort)

․화일을 표현하는 트리를 히프로 변화(완전 이진 트리)

․루트를 출력하고 나머지 트리를 다시 히프로 변환

․평균 연산 시간 [eqn: 0(n`log`n)`]

[eqn: (X_1`,`…`,`Xn )`]                               [eqn: X_1`]

[eqn: X_2`]         [eqn: X_3`]

[eqn: X_4`]      [eqn: X_5`]  [eqn: X_6`]    [eqn: X_7`]

procedure ADJUST[eqn: (i`,`n`)]

① [eqn: R` <- `R_i`;`K` <- `K_i`;`j` <- `2i`]

②  while[eqn: j`<=`n`] do

if [eqn: j<n``]and [eqn: K_j`<`K_j+1`]then [eqn: j` <- `j+1`]

③   if [eqn: K>=K`]then exit

④   [eqn: R_ꠌj/2ꠎ` <- `R_j`;`j` <- `2j`]

⑤   end

⑥   [eqn: R_ꠌj/2ꠎ ` <- `R`]

end ADJUST

[eqn: X_n-2`] [eqn: X_n-1`] [eqn: X_n`]

procedure HSORT[eqn: (R,n)`]

① for [eqn: i` <- `_ꠌ n/2_ꠎ`]to 1 by -1 do

②   dall ADJUST [eqn: (i`,n)`]

③ end

④ for [eqn: i` <- `n`-`1] to 1 by - 1 do

⑤   [eqn: T` <- `R_i+1`;` R_i+1` <- `R_1`;`R_1` <- `T`]

⑥   call ADJUST [eqn: (1`,`i)`]

⑦  end

end HSORT

예) 입력 화일(26, 5, 77, 61, 11, 59, 15, 48, 19)을 이진트리로 바꾸면

그림 (a)와 같으며, 이것을 재구성한 초기 히프가 (b)이다. 다음

(c)～(d)까지는 정렬된 화일을 나타내고 있다.

(a) 입력 화일	(b) 초기 히프

(c)                                (d)

정렬 :        77                                    66, 77

히프크기 :    i = 9                                   i = 8

*선택 정렬(selection sort)

․처음 원소부터 시작하여 순차적으로 화일 내의 값을 조사하고, 가장

크거나 작은 값을 찾아 바꾼다. 아래는 오름차순 알고리즘이다.

․평균 연산 시간  O(n2)

procedure S-SORT[eqn: (A,n)`]

① for [eqn: t` <- 1`]to [eqn: n-1`]do

②   [eqn: j ` <- `i`]

③  for [eqn: K` <- `j+1`] to [eqn: n`] do

④    if [eqn: A(K)`<`A(j)``]then [eqn: j` <- `K`]

⑤  end

⑥  [eqn: t` <- `A(i)`;` A(i)` <- `A(j)` <- `t`]

⑦  end

end S-SORT

예) 입력 화일 (26, 5, 77, 61, 11, 59, 15, 49, 19)을 선택 정렬에 의한

수행 과정을 나타내면 다음과 같다.

초기 상태 26 , 5 , 77 , 1  , 61 , 11 , 59 , 15 , 48 , 19

1단계   1 , 5 , 77 , 26 , 61 , 11 , 59 , 15 , 48 , 19

2단계   1 , 5 , 77 , 26 , 61 , 11 , 59 , 15 , 48 , 19

3단계   1 , 5 , 11 , 26 , 61 , 77 , 59 , 15 , 48 , 19

4단계   1 , 5 , 11 , 15 , 61 , 77 , 59 , 26 , 48 , 19

5단계   1 , 5 , 11 , 15 , 19 , 77 , 59 , 26 , 48 , 61

6단계   1 , 5 , 11 , 15 , 19 , 26 , 59 , 77 , 48 , 61

7단계   1 , 5 , 11 , 15 , 19 , 26 , 48 , 77 , 59 , 61

8단계   1 , 5 , 11 , 15 , 19 , 26 , 48 , 59 , 77 , 61

9단계   1 , 5 , 11 , 15 , 19 , 26 , 48 , 59 , 61 , 77

최종 단계  1 , 5 , 11 , 15 , 19 , 26 , 48 , 59 , 61 , 77

*기수 정렬(radix sort)

․여러 개의 키 K0, K1, …, Kr-1을 갖는 레코드를 정렬하는데 유용하다.

즉 기수 r를 이용하여 정렬 키를 몇 개의 숫자로 분해한다. r = 10일

때 공통 기수를 10으로 하고, 십진 분해를 수행하며,  r = 20일 때는

키를 이진  분해한다.   이 때 숫자를 정렬하기 위해  r개의 빈이 필요

하다.

․평균 연산 시간 O(d(n+r))

procedure LRSORT([eqn: R`,`n`,`d`]  )

① declare [eqn: E(0`;`r-1`)`,`F(0`;`r-1)`]

② [eqn: p` <- `1`]

③ for [eqn: i` <- `d`]to 1 by -1 do

④   for [eqn: j` <- `0`] to [eqn: r-1`]do

⑤    [eqn: F(j)` <- `0``]

⑥ end

⑦ while [eqn: p`not=`0`] do

⑧    [eqn: k` <- `K_p^i`]

⑨     if [eqn: F(k) `=` 0`] then [eqn: F(k)` <- `p`]

else [eqn: LINK(E(K))` <- `p`]

⑩     [eqn: E(k)` <- `p`]

⑪      [eqn: p` <- `LINK(p)`]

⑫ end

⑬ [eqn: j` <- `0`] : while [eqn: F(j) `=`0`] do [eqn: j` <- `j+1`] end

⑭ [eqn: p` <- `F(j)`;`t` <- `E(j)`]

⑮ for [eqn: k` <- `j+1`]to [eqn: r-1`] do

16   if [eqn: F(k)`not=`0`] then [eqn: [LINK(t)` <- `F(k)`;`t` <- `E(k)]`]

17 end

18 [eqn: LINK(t)` <- `0`]

19 end

end LRSORT

예) 입력 순서가 (179, 208, 306, 93, 859, 984, 55, 9, 271, 33)이고, 기수를

10으로 한다.   주어진 모든 수가 [0…999] 범위 안에 있으므로 필요

한 자릿수는 3이다.   입력 리스트의 원소를 R0, …, R9로 표시할 때,

다음은 각 단계에서의 정렬 상태를 보여 준다.

front[0][eqn: ->] NULL	rear[0]

front[1][eqn: ->]  271  NULL	rear[1]

front[2][eqn: ->] NULL	rear[2]

front[3][eqn: ->]  93     ∙      33   NULL	rear[3]

front[4][eqn: ->]  984  NULL	rear[4]

front[5][eqn: ->]  55   NULL	rear[5]

front[6][eqn: ->]  306  NULL                                    rear[6]

front[7][eqn: ->] NULL                                          rear[7]

front[8][eqn: ->]  208  NULL                                     rear[8]

front[9][eqn: ->]  179    ∙       859    ∙       9   NULL      rear[9]

271[eqn: ->]93[eqn: ->]33[eqn: ->]984[eqn: ->]55[eqn: ->]306[eqn: ->]208[eqn: ->]179[eqn: ->]859[eqn: ->]9

(a) i = 2인 첫 번째 단계 실행 후의 리스트

front[0][eqn: ->] 306    ∙       208    ∙       9   NULL      rear[0]

front[1][eqn: ->]NULL                                           rear[1]

front[2][eqn: ->]NULL                                           rear[2]

front[3][eqn: ->] 33   NULL                                     rear[3]

front[4][eqn: ->]NULL                                           rear[4]

front[5][eqn: ->]  55    ∙       859  NULL                     rear[5]

front[6][eqn: ->]NULL                                           rear[6]

front[7][eqn: ->]  271   ∙       179  NULL                     rear[7]

front[8][eqn: ->] 984  NULL                                     rear[8]

front[9][eqn: ->]  93  NULL                                     rear[9]

306[eqn: ->]2089[eqn: ->]33[eqn: ->]55[eqn: ->]859[eqn: ->]271[eqn: ->]179[eqn: ->]984[eqn: ->]93

(b) i = 1인 두 번째 단계 실행 후의 리스트

front[0][eqn: ->]  9   ∙     33   ∙     55  ∙     93  NULL     rear[0]

front[1][eqn: ->] 179  NULL	rear[1]

front[2][eqn: ->] 208	∙     271  NULL	rear[2]

front[3][eqn: ->] 306  NULL	rear[3]

front[4][eqn: ->]NULL	rear[4]

front[5][eqn: ->]NULL	rear[5]

front[6][eqn: ->]NULL	rear[6]

front[7][eqn: ->]NULL	rear[7]

front[8][eqn: ->] 859  NULL	rear[8]

front[9][eqn: ->] 984  NULL	rear[9]

9[eqn: ->]33[eqn: ->]55[eqn: ->]93[eqn: ->]179[eqn: ->]208[eqn: ->]271[eqn: ->]306[eqn: ->]859[eqn: ->]984

(c)[eqn: i`=`0`]인 세 번째 단계 실행 후의 리스트