프로그래밍/알고리즘

병합 정렬 (Merge Sort)

Cat체셔 2016. 5. 15. 16:12
Javascript로 구현한 Merge sort


오늘은 분할 정복 알고리즘의 기초인 MergeSort에 대해 알아보겠습니다.

MergeSort는 원소의 개수가 1개가 될때까지 나눈 후, 역순으로 2개의 그룹을 병합 정렬해 가는 알고리즘입니다. 시간 복잡도는 로 원소들의 상태에 영향을 받지 않고 안정적으로 정렬하며 정렬 전의 순서와 정렬 후의 순서가 동일함을 보장하는 stable sort입니다. 하지만 원소 개수만큼의 임시 배열을 만들어 줘야하는 단점이 있습니다.


오늘은 동영상으로 어떻게 병합정렬이 진행되는지 봅시다.



재귀로 작성한 코드

1
2
3
4
5
6
7
8
9
10
11
12
MergeSort.prototype.mergeSort = function(first, last)
{
    if(first < last)
    {
        var mid = Math.floor((last + first) * 0.5);
        this.mergeSort(first, mid);
        this.mergeSort(mid + 1, last);
 
        this.merge(first, mid, last);
    }
}
 
cs

5~6번째 줄은 앞부분과 뒷부분으로 나누는 부분입니다.

해당 함수에서는 또 앞부분과 뒷부분으로 나누면서 first<last 될때까지 나누게 될 것입니다.

그렇게 나뉘면 작은 부분부터 차례대로 merge()함수를 실행하며 올라올 것 입니다.

소그룹 정렬 => 중그룹 정렬 => 대그룹 정렬

위에 보이는 동영상처럼요.


두 그룹을 병합하는 부분(first ~ mid, mid+1 ~ last)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
MergeSort.prototype.merge = function(first, mid, last)
{
    var a = first;
    var b = mid + 1;
 
    for(var i = first ; i <= last ; ++i)
    {
        if(a > mid)
        {
            this.tempArr[i] = this.nodes[b];
            b += 1;
            continue;
        }
        else if(b > last)
        {
            this.tempArr[i] = this.nodes[a];
            a += 1;
            continue;
        }
 
 
        if(this.nodes[a].value.size < this.nodes[b].value.size)
        {
            this.tempArr[i] = this.nodes[a];
            a += 1;
        }
        else
        {
            this.tempArr[i] = this.nodes[b];
            b += 1;
        }
    }
 
    for(var i = first ; i <= last ; ++i)
    {
        this.nodes[i] = this.tempArr[i];
        this.nodes[i].value.x = 5 + i * 55;
    }
}
 
cs

두 그룹의 병합은 아주 간단합니다.

각 그룹의 첫번째 인자를 비교하여 정렬 순서대로 미리 준비한 임시 배열에 넣어줍니다.

배열에 넣은 그룹은 인덱스를 1상승시킵니다.

한쪽 그룹에 더 이상 비교할 게 없다면 나머지 한쪽 그룹을 순서대로 넣어줍니다.

모든 그룹을 임시 배열에 넣어줬다면 그것을 현재 배열에 적용합니다.


위 코드에서 임시배열은 tempArr이고, 현재 배열은 nodes입니다.

a는 first ~ mid 그룹 인덱스고, b는 mid+1 ~ last 그룹 인덱스입니다.


조심할 부분이 있다면 해당 코드는 자바스크립트라는 점입니다.

자바스크립트는 노드를 그대로 사용하면 값을 복사하기 때문에 상당히 비효율적입니다. 그래서 해당 노드를 object에 넣어서 사용해줬습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
MergeSort.prototype.createNodes = function()
{
    this.nodes = [];
    for(var i = 0 ; i < this.count ; ++i)
    {
        var node = new SortNode(i, Math.ceil(Math.random() * this.maxSize) + 1);
        node.position.x = 5 + i * 55;
        node.position.y = 600;
        this.addChild(node);
 
        this.nodes.push({value:node});
    }
}
 
cs

11번째 줄을 보시면 nodes라는 array에 {value:node}가 보이실겁니다. 이렇게 사용하시면 call by reference로 사용할 수 있다고 합니다.


For문으로 작성한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
MergeSort.prototype.sort = function*()
{
    var stack = [];
    stack.push([0, this.count-1]);
 
    for(var i = 0 ; i < stack.length ; ++i)
    {
        var lastData = stack[i];
 
        var first = lastData[0];
        var last = lastData[1];
 
        var mid = Math.floor((last + first) * 0.5);
        if(first < mid)
            stack.push([first, mid]);
        if(mid + 1 < last)
            stack.push([mid + 1, last]);
    }
 
    while(stack.length !== 0)
    {
        var data = stack.pop();
 
        this.setGroupLine(data[0], data[1]);
        yield true;
        var mid = Math.floor((data[0] + data[1]) * 0.5);
        this.merge(data[0], mid, data[1]);
        yield true;
    }
 
    this.groupLine.clear();
    yield false;
}
 
cs

위에 코드는 재귀가 아닌 For문으로 작성한 코드입니다.

작성한 이유는 다름아닌 저 동영상을 generator를 이용해 만들고 있기 때문입니다!

코드를 보시면 재귀하는 부분을 stack을 이용해 해결하였습니다. 차례대로 2등분하여 쌓아줍니다.

그리고 마지막부터 역순으로 병합해주는 형태입니다.