[TS] 타입스크립트로 구현해 본 정렬 알고리즘 #2 (병합 정렬, 퀵 정렬)

병합 정렬(Merge Sort)

병합 정렬 사진

[의미]

• 전체 원소를 하나의 단위로 분할한 후 분할한 원소들을 다시 병합하는 정렬

[특징]

• 분할 단계와 병합 단계로 나뉘어져 있으며, 분할 단계는 시간복잡도에 포함하지 않음.
• Stable한 정렬 (중복된 데이터의 순서가 바뀌지 않는 정렬)

[Big O]

• Best - O(nlog₂n)
• Worst - O(nlog₂n)

[장점]

• 데이터의 분포에 영향을 적게 받음.
• 크기가 큰 레코드를 정렬할 경우 연결 리스트(Linked List)를 사용한다면, 링크 인덱스만 변경됨으로 데이터의 이동이 엄청나게 적어지고 In-Place정렬로 구현할 수도 있다.

[단점]

• 레코드를 배열(Array)로 구현하면 Not-In-Place 정렬이 되며 추가적인 별도의 메모리를 필요로 하게 된다.

[구현]

// Array를 이용한 Not In Place 방식
function mergeSort(array:number[]) {
    if (array.length < 2) { return array;}

    const center: number = Math.floor(array.length / 2);
    const left: number[] = array.slice(0, center);
    const right: number[] = array.slice(center);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left: number[], right: number[]) {
    let result: number[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while(leftIndex < left.length && rightIndex < right.length) {
        if(left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

console.log(`Result: ${mergeSort([5,1,3,2,4])}`);

Result: 1,2,3,4,5

---

퀵 정렬(Quick Sort)

퀵 정렬 concept

[의미]

• 하나의 리스트를 기준값(pivot)을 기준으로 두 개의 리스트로 분할 하고 분할된 리스트를 정렬한 다음, 정렬된 두 개의 리스트를 합하여 정렬하는 방식. 

[특징]

• 평균적으로 매우 빠른 정렬 속도를 보인다.
• 병합 정렬과는 달리 리스트를 비균등하게 분할한다.
• 두 가지 방식으로 구현할 수 있다.
  • Not-In-Place / Stable 방식
  • In-Place / Unstable 방식

[Big O]

• Best - O(nlog₂n)
• Worst - O(n²)

[장점]

• 정렬 속도가 같은 시간복잡도를 가지는 알고리즘들과 비교했을 때도 가장 빠르다.

[단점]

• 정렬된 리스트에 대해서 오히려 수행시간이 더 많이 걸린다.(퀵 정렬의 불균형적인 분할 때문)
• 기준값(pivot)을 선정하는 방식에 따라 속도가 달라질 수 있음.

[구현]

// Not-In-Place / Stable 방식으로 구현한 퀵 정렬

function quickSort(array: number[]) {
    let pivot:number = array[0];
    let left: number[] = [];
    let right: number[] = [];

    if(array.length < 2) { return array;}

    for(let i = 1; i < array.length; i++) {
        (array[i] <= array[0]) ? left.push(array[i]) : right.push(array[i]);
    }

    return quickSort(left).concat(pivot, quickSort(right));
}

console.log(`Result: ${quickSort([5,1,3,2,4])}`);

Result: 1,2,3,4,5