Merge sort는 본래 이미 정렬된 두 개 이상의 배열을 하나의 정렬된 배열로 만드는 것으로 입력값 : 26 5 77 1 61 11 59 15 48 19
일반적으로 알고 있는 사실이다.
그러나, 정렬되지 않은 하나의 배열을 정렬하는데도 사용할 수 있다는 사실~~~!!!
정렬되지 않은 하나의 배열의 각 원소(인자) 값을 이미 정렬된 배열로 가정하여 2개씩 병합을 하면 된다.
다음과 같은 값들이 입력되었다고 하자.
이들의 병합과정은 다음과 같다.
| Pass 1 : | [26] | [5] | [77] | [1] | [61] | [11] | [59] | [15] | [48] | [19] |
| ↘ | ↙ | ↘ | ↙ | ↘ | ↙ | ↘ | ↙ | ↘ | ↙ | |
| Pass 2 : | [5 | 26] | [1 | 77] | [11 | 61] | [15 | 59] | [19 | 48] |
|
↘ |
↙ |
↘ |
↙ |
↓ | ||||||
| Pass 3 : | [1 | 5 | 26 | 77] | [11 | 15 | 59 | 61] | [19 | 48] |
|
↘ |
↙ |
↓ | ||||||||
| Pass 4 : | [1 | 5 | 11 | 15 | 26 | 59 | 61 | 77] | [19 | 48] |
|
↘ |
↙ | |||||||||
| Pass 5 : | [1 | 5 | 11 | 15 | 19 | 26 | 48 |
59 |
61 | 77] |
'IT > 알고리즘' 카테고리의 다른 글
| 기억류 auto, register, static, extern에 대한 설명. (0) | 2008.07.08 |
|---|---|
| 메모리 할당과 해제에 대한 추적 ... (0) | 2008.06.17 |
| gcov - 쓰레기 코드 찾아내기 (0) | 2008.03.11 |
| [펌] 사용자수준 쓰레드와 커널수준 쓰레드의 차이? (0) | 2008.02.27 |
| POSIX 쓰레드로 멀티 쓰레드 프로그래밍하기 (0) | 2008.02.27 |
쩐의시대
나답게 살아가고 나답게 살아가자