합병정렬(Merge Sort) 알고리즘 정리 ( 개념 / 시간복잡도 - O(nlogn) )

안녕하세요!!!!

오늘은 드디어

nlogn의 시간복잡도를 가지는 정렬 알고리즘에 대해 알아볼거에요.

먼저 결론만 말씀드리면, nlogn에 최악의 시간복잡도를 가지는 즉, O(nlogn)인 정렬 알고리즘에는

합병정렬(Merge Sort), 힙정렬(Heap Sort)이 있어요.

많이들 들어보셨죠?

처음 접하시는 분들을 위해 천천히 설명해드릴게요 XD

1. 합병정렬/병합정렬 (Merge Sort)

자.. 합병정렬을 먼저 설명드리는 이유는..

저번시간에 퀵소트 글을 썼기 때문이에요.

??그게 왜;;

라고 하실 수 있으시겠죠!!

혹시 퀵정렬이 어떤식으로 이루어지는지 기억하시나요?

네. 바로 분할정복을 통해 정렬을 하게 되는데요.

이 합병정렬도 마찬가지입니다!!!!

합병정렬은

전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬 방식입니다.

역시 말로 하니 모르겠네요. 예제를 한번 봅시다.

그 전에 밑의 gif파일을 봐주세요.

합병정렬이 어떤것인지 대충 알 수 있을 겁니다. 

자, 어떤식으로 이루어지는지 조금은 감이 오시나요?

정말 분할해서 합치는(Merge)걸 보니 이름에 걸맞네요.

위 예제를 가지고 한번 같이 해볼까요?

먼저, 합병정렬의 과정을 살펴볼게요.

1. 리스트의 길이가 1이 될때까지 반으로 잘게 나눈다.-> 분할(Divide)

2. 다 나누어 졌다면, 데이터를 합치는데(Merge), 정렬하면서 합친다. 

(작은 숫자를 앞에놓고 큰 숫자를 뒤에 놓으면 되겠죠?)

자, 과정은 끝이에요! 간단하죠? 저 과정대로 한번 해봅시다. 진짜 정렬이 되는지.

1. 리스트의 길이가 1이 될때까지 반으로 잘게 나눈다.

자, 반으로 나누래서 반으로 나눠봤어요. 리스트의 길이가 각각 4죠? 우리는 리스트의 길이가 1이 되길 원해요!!!

반으로 더 쪼개봅시다. 

계속 계속 쪼개서... 리스트의 길이가 1이 될때까지 쪼개봤어요 :)

이까지는 잘 따라오셨나요?

병합정렬이 분할정복을 통해 정렬이 이루어진다고 그랬죠?

그냥 지금은 분할(Divide)해준 것 뿐이에요!!

이렇게 과정1이 끝났습니다 XD

다음과정으로 넘어가볼까요?

2. 다 나누어 졌다면, 데이터를 합치는데(Merge), 정렬하면서 합친다. 

(작은 숫자를 앞에놓고 큰 숫자를 뒤에 놓으면 되겠죠?)

이게 무슨소리냐...

 

자 저희가 쪼갠 데이터중 제일 앞 두개를 가져와봤어요.

데이터를 합치는데 정렬하면서 합친다!

지금은 딱 두개니까 쉽네요.

5와 6을 비교하여 작은것은 앞에, 큰것은 뒤에 놓으면 되겠죠?

결과적으로, 

이렇게 되는 것입니다. 다른 것들도 똑같이 해주세요.

그러면,

자, 이렇게 되었죠? 이제 또 합쳐줘야죠.

나누어줬던 그대로 그 멤버끼리 합쳐줍시다. 

그러면, 

얘네끼리 합쳐줄 시간이네요.

앞에 있는 것 부터 같이 해볼까요? 

자, 여기서 우리는 과정2를 다시 읽어봐야합니다. 

2. 다 나누어 졌다면, 데이터를 합치는데(Merge), 정렬하면서 합친다. 

위에서는 수가 2개밖에 없어서 작은건 앞에, 

큰건 뒤에 놓으면 됐었는데, 이번엔 4개네요?

똑같습니다!! 작은건 앞에, 큰건 뒤에 놓으면 돼요!

여기서 가장 중요한것은!!!!!!!!

우리는 위에서 작은걸 앞에 두었기 때문에 

일단 두번째에 있는 것들은 안봐도 돼요.

앞에 있는 애들끼리 비교하면서 누가 더 작냐?

하고 비교하면 되는거에요!!!

1과 5가 이제 비교를 하기 시작합니다.

1과 5는 지금 자기 그룹에서 가장 작은 숫자니까요!

자 당연히 1이 더 작죠?

그러므로 1이 새로운 그룹의 제일앞에 오게됩니다. 

자, 1다음에는 그럼 5가 와야하느냐!!

아닙니다. 1이 있던 그룹의 3과 또 비교를 해야합니다. 

당연하겠죠? 

3이 현재 그룹에서는 가장 큰 숫자였지만, 

다른 그룹의 가장 작은 숫자보다도 작을 수 있으니까요.

이제 3과 5를 비교해줍니다. 

3이 더 작네요!!

바로 3이 1다음에 올 수 입니다. 

5와 6이 남았네요!!

작은 순서대로 넣어주면 되겠죠?

5, 6순으로 들어가게 됩니다. 

자, 오른쪽 그룹인 [7,8,2,4]도 똑같이 해주면

이렇게 되겠네요!!

이제 이 두 그룹을 합병 시켜 주겠습니다.

자, 현재 저 두그룹에서 가장 앞에 있는 수는 

현재 자신이 속한 그룹에서 가장 작은 숫자죠?

역시나 

1과 2를 비교해주세요 :)

1이 더 작죠? 그러므로 새 그룹의 첫 시작은 1이겠네요.

자 다음은 어떻게 하는 거였죠?

2를 바로 넣는 거였나요????

아닙니다. 

2와 3을 먼저 비교해 주어야겠죠? 

2가 더 작으니 2를 넣어줍니다. 

빨간 네모를 4로 옮기고~

3과 4를 비교하여 작은 3을 넣어주고,  

다음 비교할 대상을 3에서 5로 바꾸어 줍니다.

  

그러면 4와 5를 비교하는 거겠죠?

4가 새 그룹에 들어가게 됩니다. 

그리고 5와 7을 비교해주세요.

5가 들어가게 되겠죠? 

6과 7을 비교해줍니다. 

이제 다들 너무 잘하셔서 지겨우시겠네요..ㅎㅎ

6이 들어가게 되겠죠? 

자..!! 이제 왼쪽 그룹이 다 끝났어요 XD

오른쪽 그룹에 있는 7과 8만이 남았네요. 

만약에 이것을 소스코드로 짠다고 생각해 볼게요. 

빨간 네모는 오른쪽으로 계속 가도록 코딩을 하겠죠?

만약 현재 그룹의 끝까지 왔다면? (현재 왼쪽 그룹)

더이상 비교할 필요가 없겠죠?

왜냐하면 오른쪽 그룹에 남아있는 수들을 순서대로 넣어주기만 하면 되니까요!

이때 오른쪽에 남아있는 수들은 정렬된 상태임이 자명할겁니다.ㅎㅎㅎ

자 7과 8을 그대로 넣어줄게요!!

짜잔 ㅎㅎㅎㅎ 정렬이 끝났습니다XD

합병정렬 정말 쉽죠?

이제 가장 흥미진진한 시간인 시간복잡도를 계산해보겠습니다.

먼저 크기가 N인 배열을 반으로 쪼개면서 분할해 나가죠? 

한번 분할하면 N/2, N/2 -> 2개가 생기고,

그다음 분할하면 N/4,N/4,N/4,N/4 -> 4개

.

.

.

우리는 크기가 8인 배열로 예를 들었었죠?

최종적으로 N/8짜리가 8개 생겼었어요. 

3번만에 길이가 1인 배열을 만들어 냈다는 겁니다.

즉. 분할과정은 매번 반씩 감소하므로

밑이 2인 logN만큼 반복해야 크기가 1인 배열로 분할 할 수 있습니다.

각 분할별로 합병을 진행하므로

합병정렬의 시간복잡도는

O(NlogN)입니다. 

퀵정렬과 합병정렬은 분할정복으로 정렬을 해나간다는 점에서 공통점이 있지만,

퀵정렬은 최악의 경우 O(n^2)의 시간복잡도를 가지지만

병합정렬은 최악의 경우에도 O(nlogn)의 시간복잡도를 가진다는 것 잊지마세요!

아..원래 힙정렬도 같이 쓰려고 했는데 너무 길어져서 

다음 글에 써야할 것 같아요.

너무 글이 길어지면 보기 힘들더라구요 ㅠㅠㅠ

힙정렬로 돌아오겠습니다XD