정렬(합병정렬)
합병정렬
- 대규모 데이터에 적합
- 분할 정복 알고리즘
- 재귀를 쓰는 것이 적절하다.
EX)
[ 9, 1, 6, 8, 4, 3, 2, 0 ] |
처음상태 |
[ 9, 1, 6, 8 ] [ 4, 3, 2, 0 ] |
분할 |
[ 9, 1 ] [ 6, 8 ] [ 4, 3 ] [ 2, 0 ] |
분할 |
[ 9 ] [ 1 ] [ 6 ] [ 8 ] [ 4 ] [ 3 ] [ 2 ] [ 0 ] |
분할 |
[ 9 ] [ 1 ] [ 6 ] [ 8 ] [ 4 ] [ 3 ] [ 2 ] [ 0 ] |
분할 → 합병 |
[ 1, 9 ] [ 6, 8 ] [ 3, 4 ] [ 0, 2 ] |
합병 |
[ 1, 6, 8, 9 ] [ 0, 2, 3, 4 ] |
합병 |
[ 0, 1, 2, 3, 4, 6 ,8, 9 ] |
종료 |
[ 소스코드 ]
[ 결과창 ]
삽입병렬과 합병병렬의 차이
- 똑같이 랜덤값인 1 ~ 10000까지 주고 시간으로 비교해보았습니다.
[ 랜덤값 설정 ]
[ 삽입병렬 걸린 시간 ] - 6.7초가 걸린것을 확인할 수 있습니다.
[ 합병병렬 걸린 시간 ] - 0.3초가 걸린것을 확인할 수 있습니다.
많은 데이터가 들어올때에는 합병정렬이 더 빠르게 정렬될 수 있다는 것을 볼 수 있습니다.
