정보처리기능사 실기 알고리즘 유형#12 - 정렬병합 알고리즘

정보처리기능사 실기 알고리즘 유형 13번째 정렬과 병합 알고리즘.

Gitty up baby <3

정보처리기능사 실기 요점정리#13 - 정렬병합 알고리즘

1. 정렬 알고리즘

- 최댓값 최솟값 구하는 알고리즘과 동일. 최솟값에는 최댓값을, 최댓값에는 최솟값을 넣어서 비교!

- 오름차순 : 최솟값 부터 점점 거치는것 고로 최솟값을 구한후 최솟값을 저장또는 출력하고 최솟값이 될수없는 값 즉, 최대값으로 변이시킨후 다시루프 돌려서 그다음 작은 최솟값을 구하며 이를 반복한다.

2. 병합

- 두 배열을 합치면서 동시에 정렬하는 정렬병합 알고리즘 유형이 있는데. 주워진 두 배열이 이미 정렬되어 있다면 그냥 둘을 순서대로 비교해서 작은쪽부터 새 병합배열에 배치하면된다. 배치된 쪽 배열은 사용하면 안되므로 배열수에 +1해서 다음루프에서는 다음 배열의 수와 비교한다. 만약 둘중하나의 배열수가 맥시멈에 도달하면 비교를 포기하고 아직 맥시멈에 도달하지 않은 쪽 배열을 모두 순서대로 출력하게 한다.

만약, 두 배열이 정렬되지 않은 형태라면 하나의 정렬되지 않은 배열비교하듯 자기자신 그리고 병합할 배열 모두 전수 비교해며 최솟값 뽑아서 출력/저장하고 가상의 최대값 넣어서 지우고 루프돌리는 식으로 하면 되겠다.

예제

오름차순의 두 배열을 합병하여 오름차순 배열을 갖는 C(K)를 완성하기 위한 알고리즘은?

A(I)는 1~N 까지 B(J)는 1~M까지의 자료를 가진다. 새 배열은 C(K)이며 총 갯수는 당연히 N+M 이다.

I = 1

J = 1

K = 1

Starting Point

A(I) >= B(J) 이면 WAY1 아니면 WAY2

WAY1

C(K) = B(J)

J = J + 1

K = K + 1

만약 J = M 이면 Out Point 1로 아니면 Starting Point 로 간다.

WAY2

C(K) = A(I)

I = I + 1

K = K + 1

만약 I = N 이면 Out Point 2로 아니면 Starting Point 로 간다.

Out Point 1

반복문 I, N

C(K) = A(I)

I  = I + 1

Out Point 2

반복문 J, N

C(K) = B(J)

J = J + 1