[TS] 타입스크립트로 구현해 본 정렬 알고리즘 #1 (버블 정렬, 선택 정렬, 삽입 정렬)

정렬 알고리즘

[의미]

• 무작위로 섞여있는 데이터를 어떠한 기준에 맞추어 정리하는 알고리즘.

[사용하는 경우]

1. 각종 데이터의 목록을 정리하고 싶을 때
2. 분포도의 중위값을 알아내고 싶을 때
3. 데이터에서 중복 값을 파악하고 싶을 때
4. 이진 탐색을 하려고 할 때

[공부하는 이유]

• 기본적으로 제공되는 시스템 정렬(sort 매서드)이 항상 좋은 퍼포먼스를 보장하지는 않음.
• 환경과 상황에 걸 맞는 정렬을 사용하는 것이 중요하기 때문.

---

버블 정렬(Bubble Sort)

버블 정렬 원리 사진 (1회차 中)

[의미]

• 인접한 두 개의 데이터에 크기를 비교한 후 대소관계에 따라 두 값의 교환여부를 판단하는 알고리즘.

[특징]

• N번째 정렬 회차가 끝나면, 뒤에서 n번째 자리의 데이터가 확정됨.
• Stable한 정렬 (중복된 데이터의 순서가 바뀌지 않는 정렬)

[Big O]

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

[장점]

• In-Place 알고리즘 (데이터가 저장된 공간 내에서 정렬됨)
• In-Place 알고리즘 특성으로 추가적인 메모리를 필요로 하지 않아 메모리가 절약됨.

[단점]

• 자료의 개수가 많아질수록 성능이 매우 떨어짐.

[구현]

// Bubble Sort

function BubbleSort(...array: number[]): number[] {
    console.time();
    let swap: number;
    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length -1 -i; j++) {
            if(array[j] > array[j + 1]){
                swap = array[j];
                array[j] = array[j + 1];
                array[j + 1] = swap;
            }
        }
        console.log(array); // check
    }
    console.timeEnd();
    return array;
}

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


-----[결과]-----
[ 1, 3, 2, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
default: 5.84ms
Result: 1,2,3,4,5

---

선택 정렬(Selection Sort)

선택 정렬 사진

[의미]

• 매 회차마다 정렬이 되어 있지 않은 데이터들 중 최소값을 찾아 앞부터 차례적으로 정렬하는 알고리즘.

[특징]

• N번째 정렬 회차가 끝나면, 앞에서 n번째 자리의 데이터가 확정됨.
• UnStable한 정렬 (중복된 데이터의 순서가 바뀔수도 있는 정렬)

[Big O]

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

[장점]

• In-Place 알고리즘 (데이터가 저장된 공간 내에서 정렬됨)
• In-Place 알고리즘 특성으로 추가적인 메모리를 필요로 하지 않아 메모리가 절약됨.

[단점]

• 최선의 경우이든 최악의 경우이든, 성능이 O(n^2)으로 성능이 매우 떨어짐.

[구현]

// Selection Sort

function SelectionSort(...array: number[]) {
    console.time();
    let minIndex: number;
    let swap: number;
    for(let i = 0; i < array.length; i++) {
        minIndex = i;
        
        for(let j = i + 1; j < array.length; j++) {
            if(array[minIndex] > array[j]) { minIndex = j; }
        }

        if (minIndex != i) {
            swap = array[minIndex];
            array[minIndex] = array[i];
            array[i] = swap;
        }
        console.log(array); // check
    }
    console.timeEnd();
    return array;
}

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

-----[결과]-----
[ 1, 5, 3, 2, 4 ]
[ 1, 2, 3, 5, 4 ]
[ 1, 2, 3, 5, 4 ]
[ 1, 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
default: 5.351ms
Result: 1,2,3,4,5

---

삽입 정렬(Insertion Sort)

삽입 정렬 사진

[의미]

• 매 회차마다 기준값을 왼쪽의 정렬되어 있는 데이터들과 비교하여 올바른 위치에 삽입하는 알고리즘.

[특징]

• 기준값 왼쪽에 있는 값들이 정렬되어 있다는 가정하에 진행됨.
• Stable한 정렬 (중복된 데이터의 순서가 바뀌지 않는 정렬)

[Big O]

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

[장점]

• In-Place 알고리즘 (데이터가 저장된 공간 내에서 정렬됨)
• In-Place 알고리즘 특성으로 추가적인 메모리를 필요로 하지 않아 메모리가 절약됨.

[단점]

• 자료의 개수가 많아질수록 성능이 매우 떨어짐.

[구현]

// Insertion Sort

function InsertionSort(...array: number[]): number[] {
    console.time();
    let leftIndex : number;
    let pivot : number;
    
    for(let i = 1; i < array.length; i++) {
        pivot = array[i];
        leftIndex =  i - 1;

        while(leftIndex >= 0 && array[leftIndex] > pivot) {
            array[leftIndex + 1] = array[leftIndex];
            leftIndex--;
        }  

        array[leftIndex + 1] = pivot;
        console.log(array); // check
    }
    console.timeEnd();
    return array;
}

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

-----[결과]-----
[ 4, 5, 2, 3, 1 ]
[ 2, 4, 5, 3, 1 ]
[ 2, 3, 4, 5, 1 ]
[ 1, 2, 3, 4, 5 ]
default: 5.231ms
Result: 1,2,3,4,5

---

세 알고리즘의 시간복잡도 그래프 비교

그래프를 보았을 때, 데이터의 양이 늘어날 수록 버블 정렬이 시간이 가장 오래 걸리며, 삽입 정렬이 가장 빠름을 알 수 있다.

---

참고하면 좋은 사이트

Bubble Sort Sorting Algorithm - Big-O