병합정열 코드 해석 부탁드려요..ㅠㅠ

다른 코드로는 병합정열 이해하고 코드로도 실행시켜 봤는데 사진과 같은 방법으로 시도 하라고 하는데 이해부터 안되네요 ㅠㅠ 고수님들 이 코드 설명만 이라도 부탁드려요 ㅠㅠ

코드가 잘린것 같은데 암튼

A 는 전체 배열을 나타내고
p 는 첫 데이타 그룹의 시작위치,
q 는 첫 데이타 그룹의 끝 위치,
r 은 두 번째 데이타 그룹의 끝위치로 보입니다.

n1 인 첫 데이타 그룹의 크기는 q - p + 1 을 한 것인데, 시작데이타가 0번째고, 첫 데이타의 끝도 0번째라면 한 개 (1) 의 데이타인 셈이죠.
n2 인 두 번째 데이타 그룹의 크기는 r - q 를 한 것인데, 마지막데이타가 1번째고, 첫 데이타의 끝도 0번째라면 한 개 ( 1 ) 의 데이타인 셈이죠.
새로운 배열 2개를 생성하는데 위에서 구한 n1 n2 보다 1씩 큰 배열을 L 과 R 로 생성합니다.
하나씩 더 크게 잡는 이유는 for 문 들 아래에 나오죠.

마지막 위치 + 1 인 위치에 무한대값을 넣어서
오름차순 정렬을 할 때,
배열의 크기 비교 없이, 값의 비교만으로 끝날 수 있도록 가장 큰 값을 끝에 추가해 둔 거죠.
비교문 하나 줄이기 위한 테크닉이고요.

그 위의 2개의 for 문은 말 그대로
A 배열의 p 위치부터 q 위치까지의 값을 L 배열에 복사하고,
A 배열의 q + 1 위치부터 r 위치까지의 값을 R 배열에 복사하는 코드입니다.

즉 여기까지가 원래의 배열에서 두 개의 분할 배열로 복사한 것이고,
그 뒤 L 배열과 R 배열의 값을 비교 탐색하면서 작은쪽을 A 배열에 집어넣는 코드입니다.

infinite 상수가 없는 언어로 구현한다면 그냥 표현범위의 가장 큰 값을 적어주면 됩니다.

이건 무슨 언어인가요??

저건 의사 코드인것 같네요 ㅎㅎㅎ

1 Like