ํฉ๋ณ์ ๋ ฌ์ด๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋ ๋ณํฉ์ ๋ ฌ์ ๋ํด์ ์์๋ณด์.
1. ์ ์ ๐
๋ณํฉ์ ๋ ฌ์ด๋ ์ ๋ ฌํด์ผ ํ๋ ๋ฐฐ์ด์ ๊ฐ์ฅ ์์ ๋๊น์ง ๋๋๊ณ , ๊ทธ ์์ ๋ถํฐ ์ธ์ ํ ๋ถ๋ถ๋ฐฐ์ด๋ผ๋ฆฌ ๋น๊ตํ๋ฉฐ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
ํด๋น ์๊ณ ๋ฆฌ์ฆ์ ๋ถํ ์ ๋ณต(Divide and Conquer) ์๊ณ ๋ฆฌ์ฆ์ ๊ธฐ๋ฐ์ผ๋ก ํ๋ค. (๋ถํ ์ ๋ณต(Divide and Conquer)์ด๋ ๋ฌธ์ ๋ฅผ ๋ถํ ํ๊ณ , ๋ถํ ํ ๋ฌธ์ ๋ฅผ ์ ๋ณตํ์ฌ ํฉ์น๋ ๊ฒ์ด๋ค.)
2. ๋์ ๋ฐฉ์ ๐ช
- ์ฃผ์ด์ง ๋ฐฐ์ด์ ์ ๋ฐ์ผ๋ก ๋ถํ ํ์ฌ ๋ถ๋ถ๋ฐฐ์ด๋ก ๋๋๋ค. - ๋ถํ (Divide)
- ํด๋น ๋ถ๋ถ๋ฐฐ์ด์ ๊ธธ์ด๊ฐ 1์ด ๋ ๋๊น์ง ๊ณ์ํด์ 1๋ฒ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
- ์ธ์ ํ ๋ถ๋ถ ๋ฐฐ์ด๋ผ๋ฆฌ ํฉ์น๋ค. - ์ ๋ณต(Conquer)
์์ ๊ทธ๋ฆผ์ ํตํด ์ ์ ์๋ฏ์ด ํฌ๊ธฐ๊ฐ 1์ด ๋ ๋๊น์ง ๋ถํ ์ด ์งํ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ธ์ ํ ๋ฐฐ์ด๋ผ๋ฆฌ ํฉ์น๋ฉด์ ๊ณ์ํด์ ์ ๋ ฌ์ด ์ด๋ฃจ์ด์ง๋ค. ๊ทธ๋ฌ๋ฉด ์ต์ข ์ ์ผ๋ก ์ ๋ ฌ๋ ๋ฐฐ์ด์ ์ป์ ์ ์๋ค. ๋ณํฉํ ๋ ์ด๋ป๊ฒ ์ ๋ ฌ์ด ๋๋์ง "๋ง์ง๋ง conquer ๊ณผ์ ์ธ '2 4 6 8'๊ณผ '3 5 7 9'๋ฅผ ๋ณํฉํ๋ ๊ณผ์ "์ ํตํด ์กฐ๊ธ ๋ ์์ธํ ์์๋ณด์.
ํฉ๋ณ์ ์ํฌ ๋ ๊ฐ์ ๋ฐฐ์ด์ ์ด๋ฏธ ์ ๋ ฌ์ด ๋์ด ์๋ ์ํ์ด๋ค. ๊ทธ๋ฌ๋ฏ๋ก ๋ณํฉ์ ํ๋ ๊ณผ์ ์์๋ ์์ ์ด ์ํ ๋ฐฐ์ด์ ์์๋ค๊ณผ ๋น๊ต๋ฅผ ํ ํ์ ์์ด ์ธ์ ํ ๋ถ๋ถ ๋ฐฐ์ด์ ์์๋ค๋ง ๋น๊ต๋ฅผ ํด์ฃผ๋ฉด ๋๋ค. ์์๋ผ๋ฆฌ ๋น๊ต๋ฅผ ํด๋๊ฐ๋ฉด์ ์์ ๊ฒ์ด ๋จผ์ ๋ฐฐ์น๋๋ค๊ณ ์๊ฐํ๋ฉด ๋๋ค.
์์์์๋ ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ์ด ์์๋๋ก ํ ๊ฐ์ฉ ์ ํ์ด ๋๊ณ ์๋๋ฐ, ๊ผญ ๊ทธ๋ฐ ๊ฒ๋ง์ ์๋๋ค. ๋น๊ต๋ฅผ ํตํด ์์ ๊ฑฐ๋ฅผ ์ ํํ๋ ๊ฒ์ด๋ค. '2 8'๊ณผ '4 6'์ด ๋ณํฉ๋๋ ๊ฒ์ ๋ณด๋ฉด ์ฝ๊ฒ ์ ์ ์๋ค.
3. ๊ตฌํ(JAVA) ๐ญ
public void main(String[] args) {
int[] array = {8, 2, 6, 4, 7, 3, 9, 5};
mergeSort(array, 0, array.length - 1);
}
void mergeSort(int[] array, int left, int right) {
// ๋ ์ด์ ๋ถํ ํ ์ ์๋ ๊ฒฝ์ฐ
// (ํฌ๊ธฐ๊ฐ 1์ธ ๊ฒฝ์ฐ)
if(left == right) {
return;
}
int mid = (left + right) / 2;
// ๋ถํ (Divide)
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
// ๋ถํ ๋ ๋ฐฐ์ด์ ๋ณํฉํ๊ธฐ - ์ ๋ณต(Conquer)
merge(array, left, mid, right);
}
// ๋ถํ ๋ ๋ฐฐ์ด์ ๋ณํฉํด์ฃผ๋ ๊ณผ์ ์์
// ์ ๋ ฌ์ด ์ด๋ฃจ์ด์ง๋ค.
void merge(int[] array, int left, int mid, int right) {
// ์ผ์ชฝ ๋ถ๋ถ๋ฐฐ์ด
int[] L = Arrays.copyOfRange(array, left, mid + 1);
// ์ค๋ฅธ์ชฝ ๋ถ๋ถ๋ฐฐ์ด
int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
// ์ผ์ชฝ ๋ถ๋ถ๋ฐฐ์ด์ ์ธ๋ฑ์ค ๋ฒํธ
int l = 0;
// ์ค๋ฅธ์ชฝ ๋ถ๋ถ๋ฐฐ์ด์ ์ธ๋ฑ์ค ๋ฒํธ
int r = 0;
// ๋ณํฉ๋์ด์ง ๋ฐฐ์ด์ ์ธ๋ฑ์ค ๋ฒํธ
int idx = left;
int leftLength = L.length;
int rightLength = R.length;
// ๋ ๊ฐ์ ๋ฐฐ์ด์์ ์์๋ฅผ ๋น๊ตํด์ผ ํ๋ ๊ฒฝ์ฐ
// ๊ฐ๊ฐ์ ๋ฐฐ์ด์ ์ ๋ ฌ๋์ด์ง ์ํ์ด๋ฏ๋ก, ๋ ๊ฐ์ ๋ฐฐ์ด์ ์์๋ง ๋น๊ตํ๋ฉด ๋จ
while(l < leftLength && r < rightLength) {
if(L[l] <= R[r]) {
array[idx] = L[l++];
}
else {
array[idx] = R[r++];
}
idx++;
}
// ์ผ์ชฝ ๋ถ๋ถ๋ฐฐ์ด์ด ๋จ์ ์๋ ๊ฒฝ์ฐ
// ๋ณํฉํ์ฌ ๋ง๋ค์ด์ง ๋ฐฐ์ด์ ๋ฃ๊ธฐ
while(l < leftLength) {
array[idx++] = L[l++];
}
// ์ค๋ฅธ์ชฝ ๋ถ๋ถ๋ฐฐ์ด์ด ๋จ์ ์๋ ๊ฒฝ์ฐ
// ๋ณํฉํ์ฌ ๋ง๋ค์ด์ง ๋ฐฐ์ด์ ๋ฃ๊ธฐ
while(r < rightLength) {
array[idx++] = R[r++];
}
}
4. ์๊ฐ๋ณต์ก๋ & ๊ณต๊ฐ๋ณต์ก๋ ๐
1. ์๊ฐ๋ณต์ก๋
'๋ถํ 'ํ ๋์ '๋ณํฉ(์ ๋ณต)'ํ ๋๋ฅผ ๋๋์ด์ ์๊ฐํด ๋ณด์.
[๋ถํ ]
ํฌ๊ธฐ๊ฐ 1์ธ ๋ฐฐ์ด๊น์ง ๋ถํ ์ ํด์ผ ํ๋ฏ๋ก ํ์ ๋ ฌ์ ์ํด์ O(logN)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค.
[๋ณํฉ(์ ๋ณต)]
i๋ฒ์งธ ๋ ๋ฒจ์๋ 2^i๊ฐ์ ๋ถ๋ถ๋ฐฐ์ด์ด ์๋ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ ๋ถ๋ถ๋ฐฐ์ด์๋ N / 2^i ๊ฐ์ ์์๊ฐ ์๋ค. ํ๋์ ๋ณํฉ๋ ๋ฐฐ์ด์ ๋ง๋ค๊ธฐ ์ํด์๋ ๋ ๊ฐ์ ๋ถ๋ถ ๋ฐฐ์ด์ ์์ ๊ฐ์๋งํผ ๋น๊ตํ์ฌ ๋ง๋ค ์ ์๋ค.
๊ทธ๋ฌ๋ฉด i๋ฒ์งธ ๋ ๋ฒจ์์ ํ๋์ ๋ณํฉ๋ ๋ฐฐ์ด์ ๋ง๋ค๊ธฐ ์ํด์๋ N / 2^i * 2์ ๋น๊ต๊ฐ ์ผ์ด๋๊ณ , ์ด 2^i / 2๋ฒ ํด์ค์ผ ํ๋ค.
(N / 2^i * 2) * ( 2^i / 2) = N
๊ทธ๋ฆฌ๊ณ ์ด๊ฒ์ ํธ๋ฆฌ์ ๋์ด์ธ logN๋ฒ ์ํํด์ผ ํ๋ฏ๋ก ์ต์ข ์ ์ผ๋ก O(N logN)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค.
๊ทธ๋ฌ๋ฏ๋ก ์๊ฐ๋ณต์ก๋๋ O(N logN)์ด๋ค.
์ต์ (BEST) | ํ๊ท (AVERAGE) | ์ต์ (WORST) | |
์๊ฐ๋ณต์ก๋ | O(N logN) | O(N logN) | O(N logN) |
2. ๊ณต๊ฐ๋ณต์ก๋
์ ๋ ฌํ ๋ฐฐ์ด๊ณผ ๊ฐ์ ํฌ๊ธฐ์ N์ ์๋ก์ด ๋ฐฐ์ด์ด ํ์ํ๋ฏ๋ก ๊ณต๊ฐ๋ณต์ก๋๋ O(2N)์ด๋ค.
5. ์ฅ์ & ๋จ์ ๐ฅ
1. ์ฅ์
- ์ต์ ์ ๊ฒฝ์ฐ์๋ ์๊ฐ๋ณต์ก๋๊ฐ O(N log N)์ด๋ค
- ์์ ์ ๋ ฌ์ด๋ค.
2. ๋จ์
- ์ถ๊ฐ์ ์ธ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ํ์ํ๋ค.
- ๋ณด์กฐ ๋ฐฐ์ด์์ ์๋ณธ๋ฐฐ์ด๋ก ๋ณต์ฌํ๋ ๊ณผ์ ์ ๋งค์ฐ ๋ง์ ์๊ฐ์ ์๋นํ๊ธฐ ๋๋ฌธ์ ๋ฐ์ดํฐ๊ฐ ๋ง์ ๊ฒฝ์ฐ ์๋์ ์ผ๋ก ์๊ฐ์ด ๋ง์ด ์์๋๋ค.
ํด๋น ๊ธ์ Stranger๋์ ํฉ๋ณ์ ๋ ฌ/๋ณํฉ์ ๋ ฌ(Merge Sort)์ ์ฐธ๊ณ ํ์์ต๋๋ค.
'๐ ์๋ฃ๊ตฌ์กฐ > ์ ๋ ฌ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ ์ ๋ ฌ (Heap Sort) (0) | 2023.03.12 |
---|---|
์์ ์ ๋ ฌ(Topology Sort) (2) | 2023.03.07 |
์ฝ์ ์ ๋ ฌ(Insertion Sort) (0) | 2023.03.06 |
์ ํ ์ ๋ ฌ(Selection Sort) (2) | 2023.03.04 |
๋ฒ๋ธ ์ ๋ ฌ(Bubble Sort) (0) | 2023.03.04 |