Blog

[알고리즘] 병합정렬

On 8 10월, 2016 By With 0 Comments

병합정렬
병합 알고리즘을 사용한 정렬로 n/2로 리스트n을 쪼개질때까지 나눈다음 쪼개진 원소간 비교연산 후 병합하는 과정을 거친다.
재귀(splitData)를 사용하여 리스트를 n/2로 쪼개며 쪼개진 데이터를 값 비교 및 병합하는 분할정복(mergeData)을 수행하여 값을 정렬한다.
분할정복이 끝나면 정렬된 리스트를 얻을 수 있다.

JavaScript
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
// 데이터를 반으로 쪼갠다
function splitData(aData){
    if(aData.length < 2) {
        return aData;
    }
 
    var nMiddleIndex = Math.floor(aData.length / 2),
        aLeft = aData.slice(0, nMiddleIndex),
        aRight = aData.slice(nMiddleIndex, aData.length);
    
    // 재귀로 리스트를 분할한다.
    return mergeData(splitData(aLeft), splitData(aRight));
}
 
// 데이터를 머지한다
function mergeData(aLeft, aRight){
    var aResult = [];
    
    while(aLeft.length && aRight.length){
        if(aLeft[0] <= aRight[0]){
            aResult.push(aLeft.shift());
        }else{
            aResult.push(aRight.shift());
        }    
    }
 
    while(aLeft.length){
        aResult.push(aLeft.shift());
    }
 
    while(aRight.length){
        aResult.push(aRight.shift());
    }
    
    return aResult;
}
 
var aData = [6,5,4,1,3,2];
splitData(aData);

*해당 포스트는 알고리즘 학습을 위한 포스트로 정확하지 못한 개념과 코드가 있을 수 있습니다. 익숙한 언어인 js로 코드를 작성하였는데 개념이나 적절하지 못한 코드는 코멘트 들아주시면 감사하겠습니다 ^^

 

, ,