1. ๋ณํฉ ์ ๋ ฌ์ ๋ฌด์์ธ๊ฐ?
๋ณํฉ ์ ๋ ฌ์ (1) ์ธ์ธํ๊ฒ ๋๋๋ค.
โ (2) ํ๋์ฉ ์ ๋ณตํ๋ค
์ ๋ฐฉ์์ผ๋ก ์ ๋ ฌ๋์ง ์์ ์ผ๋ จ์ ๋ฐ์ดํฐ๋ฅผ ์ ๋ ฌ์ํค๋ ๋ฐฉ๋ฒ์ด๋ค.
2. ์๋ฆฌ
๋ค์ 3๊ฐ์ง ์์๋ฅผ ๋ฐ๋ผ์ ์งํ๋๋ค.
(1) *๋ ์ด์ ์ชผ๊ฐค ์ ์์ ๋๊น์ง ๋ฐ์ดํฐ๋ฅผ ๋ถ๋ฆฌ์ํจ๋ค.* ( ๋ถํ by ์ฌ๊ท
)
(2) ์ธ์ ํ ๋ฐ์ดํฐ ๊ทธ๋ฃน๋ผ๋ฆฌ ๋์๊ด๊ณ ๋น๊ต๋ฅผ ํตํด ์ ๋ ฌ์ํจ๋ค. (์ ๋ณต by ํฌ ํฌ์ธํฐ
)
(3) ์ ๋ ฌ๋ ๋ฐ์ดํฐ๋ฅผ ๋ค์ ํ๋์ ๊ทธ๋ฃน์ผ๋ก ๊ฐ์ฃผํ๊ณ , ๋ฐ์ดํฐ ์ ์ฒด๊ฐ ํ๋์ ๊ทธ๋ฃน์ด ๋ ๋๊น์ง (2)๋ฒ์ ๋ฐ๋ณตํ๋ค.
3. ์์
๋น ์ ๋ ฌ๋ ์ผ๋ จ์ ๋ฐ์ดํฐ๋ฅผ ์์ ๋ฐฉ์์ ์ฐจ๋ก๋๋ก ์ํํ์ฌ ์ ๋ ฌ์์ผ๋ณด๊ฒ ๋ค.7, 2, 4, 3, 1, 5, 6
์ ์ผ๋ จ์ ๋ฐ์ดํฐ๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ์ํจ๋ค๊ณ ๊ฐ์ ํด๋ณด์.
(1) ๋ถํ by ์ฌ๊ท
์ฌ๊ท๋ฅผ ํตํด ๋ฐ์ดํฐ๋ค์ ๋ ์ด์ ์ชผ๊ฐค ์ ์์ ๋๊น์ง ๋๋๋ค. ๋จ์ ์ซ์๋ก ์ด๋ฃจ์ด์ง ์์ ์์์์๋ ์ซ์๋ฅผ ํ๋ ํ๋์ฉ ๋๋๋ ๊ฒ์ด ๊ทนํ์ผ๋ก ๋๋๋ ๊ฒ์ผ ๊ฒ์ด๋ค. ์ด๋ ๊ฒ ๋๋๋ ์ฝ๋๋ ๋ค์ ์ฅ์์ ์์ธํ ๋ค๋ฃจ๊ฒ ๋ค. ์ผ๋จ ์ฌ๊ท๋ฅผ ํตํด ๋ฐ์ดํฐ๋ฅผ ํ๋ ํ๋ ๋๋ ์ํ๋ผ๊ณ ์๊ฐํ์.
(2) ์ ๋ณต by ํฌ ํฌ์ธํฐ
์ด์ ๋ฐ์ดํฐ๋ค์ ํฌ ํฌ์ธํฐ๋ฅผ ํ์ฉํด ํ๋์ฉ ์ ๋ ฌํ๊ณ ๋ฌถ์ ๊ฒ์ด๋ค. ์ด๋ ๋ฐ์ดํฐ ๊ทธ๋ฃน์ ์ ๋ ฌ๋ ์ซ์์ ๋ฌถ์
์ด๋ผ๊ณ ๊ฐ์ฃผํ๊ฒ ๋ค. ๋ฐ์ดํฐ๊ฐ ํ๋์ฉ ๋๋ ์ํ์์๋ ๋์๊ด๊ณ ๋น๊ตํ ๊ฒ์ด ์์์ผ๋ก ๊ฐ๊ฐ์ด ์ ๋ ฌ๋ ์ซ์์ ๋ฌถ์์ด๋ค. ์ธ์ ํ ๋ ๊ฐ์ ๋ฐ์ดํฐ ๊ทธ๋ฃน๋ผ๋ฆฌ ๋์๊ด๊ณ๋ฅผ ๋น๊ตํ์ฌ ์ ๋ ฌํ๋ค๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๋ ๊ฒ์ด๋ค.
์ฌ๊ท๋ฅผ ํด๋ณด๋ฉด ์๊ฒ ์ง๋ง, 7์ (2,4), (6,5), (1,3) ๋ฌถ์๊ณผ ๊ฐ์ ๋ ๋ฒจ์ด๋ค. ์ฌ๊ท์์ ์ ์ผ ๊น์ ๋ ๋ฒจ์ 2์ 4, 6๊ณผ 5, 1๊ณผ 3 ๋น๊ต์ผ ๊ฒ์ด๋ค. ์ด๋ค์ ๋์๊ด๊ณ ๋น๊ต ํ ์์ ๋ณด๋ผ์ ๊ทธ๋ฆผ์ฒ๋ผ ์ ๋ ฌ๋์๋ค.
ํ์ฌ๋ ๋จ์ 1:1 ๋น๊ต๋ผ์ ํฌ ํฌ์ธํฐ ํ์ฉ์ด ์ ๋ณด์ด์ง ์๋๋ค. ํ์ง๋ง 1๊ฐ ์ด์์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ง ๊ทธ๋ฃน๊ฐ์ ๋์๊ด๊ณ ๋น๊ต๊ฐ ํ์ํ ๋ค์ ์งํ์ํฉ๋ถํฐ๋ ํฌ ํฌ์ธํฐ์ ์ฌ์ฉ์ด ํ์์ ์ด๋ค. (5,6) ๊ทธ๋ฃน๊ณผ (1,3)๊ทธ๋ฃน์ ๋น๊ต๋ฅผ ๋ณผ๊น?
L
ํฌ์ธํฐ๋ ์ผ์ชฝ ๊ทธ๋ฃน, R
ํฌ์ธํฐ๋ ์ค๋ฅธ์ชฝ ๊ทธ๋ฃน, E
ํฌ์ธํฐ๋ ๋ ๊ทธ๋ฃน์ด ์ ๋ ฌ๋์ด ๋ค์ด๊ฐ ํ๋์ ๊ทธ๋ฃน์์ ์์ง์ด๋ ํฌ์ธํฐ๋ผ๊ณ ํด๋ณด์.
์ฌ๊ธฐ์ (1) L๊ณผ R์ด ๊ฐ๋ฆฌํค๋ ๊ฐ์ ๋น๊ต ํ, (2) ๋ ์์ ๊ฐ์ด E ํฌ์ธํฐ ์์น์ ์ฝ์ ๋๊ณ , (3) ์ฌ์ฉ๋ ํฌ์ธํฐ๋ ํ ์นธ ์์ผ๋ก ์ ์งํ๋ค.
๋ฐ๋ผ์ ์์์๋ ๋ ์์ 1์ด E๊ฐ ๊ฐ๋ฆฌํค๋ ์์น์ ์ฝ์ ๋ ๊ฒ์ด๊ณ , R๊ณผ E ํฌ์ธํฐ๊ฐ ํ ์นธ ์์ผ๋ก ์ ์งํ ๊ฒ์ด๋ค.
๋ ๊ทธ๋ฃน ๊ฐ์ ์ ๋ ฌ์ ๋๊น์ง ํ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๋๋ค.
์ ์ฒด ์ซ์์ ๋ํด์ ํ๋ฉด ๋ค์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ ๋ ฌ๋ ๊ฒ์ด๋ค.
4. ์ฝ๋
์์๋ ๊ทธ๋ฃน์ด ๋ค๋ฅด๊ฒ ๋๋์ด์ง๊ธด ํ์ง๋ง(?) ๋ค์ ์ฝ๋๋ฅผ ์ฐธ๊ณ ํ์ฌ ๋ง๋ฑ๋จ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์ ๋ง๊ฒ ๋ณํํ์ฌ ํ์ด๋ด๊ธธ ๋ฐ๋๋ค.
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int [] arr = new int [] {7,2,4,6,5,1,3};
static int [] tmp = new int [7];
public static void main(String[] args) throws IOException {
merge_sort(0, 6, 0);
}
public static void merge_sort (int start, int end, int depth) {
// 0. ๊ธฐ์ ์กฐ๊ฑด
if(start == end) return;
int mid = (start+end)/2;
// 1. ๋ถํ by ์ฌ๊ท
merge_sort(start, mid, depth+1);
merge_sort(mid+1,end, depth+1);
// 2. ์ ๋ณต by ํฌ ํฌ์ธํฐ
// 2-1 ์ด์ ๊ณ์ฐ์ ์ํ ๋ฐฉํด๋ฅผ ๋ฐ์ง ์๊ธฐ ์ํด ์ ๋ ฌํ ๊ฐ๋ค์ ์์๋ฐฐ์ด์ ์ ์ฅ
System.arraycopy(arr, 0, tmp, 0, 7);
int L = start;
int R = mid+1;
int E = start;
// ์ถ๋ ฅ ๋ถ๋ถ------------------------------------------
System.out.println("์ฌ๊ท ๊น์ด: " + depth);
System.out.println("์ ๋ ฌ ์ - "+ Arrays.toString(arr));
System.out.print("์ผ์ชฝ ๊ทธ๋ฃน: " );
for (int i = start; i < R; i++) {
System.out.print(tmp[i] + " ");
}
System.out.print(" vs ์ค๋ฅธ์ชฝ ๊ทธ๋ฃน: " );
for (int i = mid+1; i <=end; i++) {
System.out.print(tmp[i] + " ");
}
System.out.println();
// ------------------------------------------------
while (L <= mid && R <= end){
if(tmp[L] <= tmp[R]) arr[E++] = tmp[L++];
else arr[E++] = tmp[R++];
}
if(L <= mid){
for (int i = L; i <= mid; i++) {
arr[E++] = tmp[i];
}
}
// ์ถ๋ ฅ ๋ถ๋ถ ----------------------------------------------
System.out.println("์ ๋ ฌ ํ- "+ Arrays.toString(arr));
System.out.println();
// -------------------------------------------------------
}
}
5. ๋ฌธ์ ์ถ์ฒ