이보다 수행시간을 더 줄일 수 있는 방법은 있을까? 물론, 존재한다.
이번장에서는 병합 정렬(Merge Sort)에 대해서 알아보도록 하겠다.
병합정렬이란 N개의 원소들중에서 가운데를 기준으로 반반씩 나눈 뒤에
앞의 원소들은 전반부, 뒤의 원소들은 후반부로 가정을하며, 이 전반부, 후반부가 각각 N개, N/2개, N/4개 ... 2개, 1개가 남을때까지 나누어주는 분리과정, 그리고 분리과정을 통해 나온 원소의 수를 1개씩, 2개씩.. n/2개씩 n개씩 비교하면서 정렬시키는 병합과정이 필요하다.
(분리과정, 병합과정 2개의 알고리즘이 필요하다)
조금 더 자세히 알아보면...
Ex) 병합정렬 과정
A = { 5, 4, 9, 2, 7, 1, 6, 3 }
1회 분리( 5, 4, 9, 2, 7, 1, 6, 3 )
: 전반부 ▶ 5, 4, 9, 2 & 후반부 ▶ 7, 1, 6, 3
2회 분리( 5, 4, 9, 2 )
: 전반부 ▶ 5, 4 & 후반부 ▶ 9, 2
3회 분리( 5, 4 )
: 전반부 ▶ 5 & 후반부 ▶ 4 - 분리완료
4회 분리( 9, 2 )
: 전반부 ▶ 9 & 후반부 ▶ 2 - 분리완료
5회 분리( 7, 1, 6, 3 )
: 전반부 ▶ 7, 1 & 후반부 ▶ 6, 3
6회 분리( 7, 1 )
: 전반부 ▶ 7 & 후반부 ▶ 1 - 분리완료
7회 분리( 6, 3 )
: 전반부 ▶ 6 & 후반부 ▶ 3 - 분리완료
여기까지 분리가 완료된다면(전반부, 후반부가 하나의 원소가 남을경우) 병합을 실행
병합은 전반부의 원소들과 후반부의 원소들의 앞부분을 병합하며 정렬시켜 나아감
1회 병합 (전반부 : 5 / 후반부 : 4)
▶ 4 ( 5 / 4 )
▶ 4, 5 ( 5 / ) - 병합완료
2회 병합 (전반부 : 9 / 후반부 : 2)
▶ 2 ( 2 / 9 )
▶ 2, 9 ( / 9 ) - 병합완료
3회 병합 (전반부 : 4, 5 / 후반부 : 2, 9)
▶ 2 ( 4, 5 / 2, 9 )
▶ 2 ( 4, 5 / 2, 9 )
▶ 2, 4 ( 4, 5 / 9 )
▶ 2, 4, 5 ( 5 / 9 )
▶ 2, 4, 5, 9 ( / 9 ) - 병합완료
▶ 2, 4, 5 ( 5 / 9 )
▶ 2, 4, 5, 9 ( / 9 ) - 병합완료
4회 병합 (전반부 : 7 / 후반부 : 1)
▶ 1 ( 7 / 1 )
▶ 1, 7 ( 7 / ) - 병합완료
5회 병합 (전반부 : 6 / 후반부 : 3)
▶ 3, ( 6 / 3 )
▶ 3, 6 ( 6 / ) - 병합완료
6회 병합 (전반부 : 1, 7 / 후반부 : 3, 6)
▶ 1 ( 1, 7 / 3, 6 )
▶ 1, 3, ( 7 / 3, 6 )
▶ 1, 3, 6 ( 7 / 6 )
▶ 1, 3, 6, 7 ( 7 / ) - 병합완료
▶ 1, 3, 6 ( 7 / 6 )
▶ 1, 3, 6, 7 ( 7 / ) - 병합완료
7회 병합 (전반부 : 2, 4, 5, 9 / 후반부 : 1, 3, 6, 7)
▶ 1 ( 2, 4, 5, 9 / 1, 3, 6, 7 )
▶ 1, 2 ( 2, 4, 5, 9 / 3, 6, 7 )
▶ 1, 2, 3 ( 4, 5, 9 / 3, 6, 7 )
▶ 1, 2, 3, 4 ( 4, 5, 9 / 6, 7 )
▶ 1, 2, 3, 4, 5 ( 5, 9 / 6, 7 )
▶ 1, 2, 3, 4, 5, 6, ( 9 / 6, 7 )
▶ 1, 2, 3, 4, 5, 6, 7 ( 9 / 7 )
▶ 1, 2, 3, 4, 5, 6, 7, 9 ( 9 / ) - 병합완료
▶ 1, 2 ( 2, 4, 5, 9 / 3, 6, 7 )
▶ 1, 2, 3 ( 4, 5, 9 / 3, 6, 7 )
▶ 1, 2, 3, 4 ( 4, 5, 9 / 6, 7 )
▶ 1, 2, 3, 4, 5 ( 5, 9 / 6, 7 )
▶ 1, 2, 3, 4, 5, 6, ( 9 / 6, 7 )
▶ 1, 2, 3, 4, 5, 6, 7 ( 9 / 7 )
▶ 1, 2, 3, 4, 5, 6, 7, 9 ( 9 / ) - 병합완료
그렇다면 수행시간을 얼마나 단축시킬 수 있겠는가?
우선 기초적인 정렬(선택, 버블, 삽입)을 사용했을경우, 100개의 원소가있다면 1부터 N까지 숫자들을 비교 후 큰 수를 뒤로 보내거나(선택, 버블) 앞에서부터 하나씩 비교하며 정렬시켜 나아갈 것이다(삽입). 이렇게 된다면 상당히 긴 수행시간이 소요될 것이다.
그렇다면 병합정렬을 사용하게 된다면?
100개의 원소가있다면, 100개 → 50개 → 25개 → 12개 → 6개 → 3개 → 1개의 원소가 남을때까지 나누고, 1개 → 3개 → 6개 → 12개 → 25개 → 50개 → 100개가 될때까지 나눈 숫자들을 다시 병합하며 정렬이 되는것이다.
평균적으로 Theta(nlogn)의 시간이 소요된다.
알고리즘을 보면..
▶실행결과
댓글 없음:
댓글 쓰기