직접적인 비교 정렬

이들 알고리즘은 데이터의 순서를 변경하거나 선택하여 직접 정렬하는 방식을 사용한다.

하위의 알고리즘의 구현하기 쉬운게 장점이지만, 성능은 O(n^2)로 좋지 못하다.

버블 정렬 (Bubble Sort)

데이터를 옆 데이터와 비교하면서 자리를 바꾸는 형식이 거품이 일어나는 것 같다고 해서 버블 정렬이라는 이름이 붙었다.

동작 원리

1. 리스트의 처음부터 끝까지 인접한 원소들을 비교한다.
2. 만약 인접한 두 원소가 정렬되어 있지 않다면, 그 두 원소의 위치를 바꾼다.
3. 리스트의 끝까지 도달할 때까지 1과 2의 과정을 반복한다.
4. 위의 과정을 리스트의 원소 개수만큼 반복한다.

구현

    for(let i = 0; i < arr.length - 1; i++){
        for(let j = 0; j < (arr.length - i - 1); j++){
            if(arr[j] > arr[j + 1]){
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

선택 정렬 (Selection Sort)

주어진 데이터에서 가장 작은 (또는 큰) 값을 선택하여 알맞은 위치에 배치하는 방식으로 동작하는 정렬 알고리즘이다.

동작 원리

1. 주어진 리스트에서 가장 작은 원소를 찾는다.
2. 해당 원소와 리스트의 첫 번째 원소의 위치를 바꾼다.
3. 리스트의 나머지 부분에서 가장 작은 원소를 찾고, 그 원소와 리스트의 두 번째 원소를 교체한다.
4. 위의 과정을 리스트의 원소 개수만큼 반복한다.

구현

function SelectionSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        let minValueIndex = i;

        for(let j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[minValueIndex]){
                minValueIndex = j;
            }
        }

        let temp = arr[i];
        arr[i] = arr[minValueIndex];
        arr[minValueIndex] = temp;
    }
}

삽입 정렬 (Insertion Sort)

주어진 데이터를 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 하나씩 정렬된 부분의 알맞은 위치에 삽입하는 방식으로 동작하는 정렬 알고리즘이다.

동작 원리

1. 리스트의 첫 번째 원소는 이미 정렬된 부분이라고 가정한다.
2. 다음 원소(정렬되지 않은 부분의 첫 원소)를 선택한다.
3. 이 원소를 정렬된 부분의 알맞은 위치에 삽입한다.
4. 위의 과정을 리스트의 마지막 원소까지 반복한다.

function InsertionSort(arr){
    for(let i = 1; i < arr.length; i++){
        let insertingData = arr[i];
        let j;
        for(j = i - 1; j >= 0; j--){
            if(arr[j] > insertingData){
                arr[j + 1] = arr[j];
            }else{
                break;
            }
        }
        arr[j + 1] = insertingData;
    }
}

분할 정복(Divide and Conquer) 전략

이 알고리즘은 '분할 정복' 전략을 사용하여 문제를 더 작은 부분으로 나눈 다음, 각 부분 문제를 해결하고 결합하여 전체 문제를 해결한다.
위의 정렬 방식보다 구현은 복잡하지만 더 좋은 성능을 갖고 있다.

병합 정렬 (Merge Sort)

기본 원리

1. 분할 (Divide) : 주어진 리스트를 두 개의 균등한 크기의 하위 리스트로 분할한다. 이 하위 리스트는 주어진 리스트의 연속적인 원소들로 구성된다.
2. 정복 (Conquer) : 두 개의 하위 리스트를 각각 재귀적으로 병합 정렬한다.
3. 병합 (Merge) : 두 개의 하위 리스트를 병합하여 하나의 정렬된 리스트를 만든다.

특징

• 모든 경우에 대해 O(n log n)의 시간 복잡도를 가진다.
• 병합 과정에서 메모리 공간이 필요하다.

구현

function MergeSort(arr, leftIndex, rightIndex){
    if(leftIndex < rightIndex){
        let midIndex = parseInt((leftIndex + rightIndex) / 2);
        MergeSort(arr, leftIndex, midIndex);
        MergeSort(arr, midIndex + 1, rightIndex);
        Merge(arr, leftIndex, midIndex, rightIndex);
    }
}

function Merge(arr, leftIndex, midIndex, rightIndex){
    let leftAreaIndex = leftIndex;
    let rightAreaIndex = midIndex + 1;

    let tempArr = [];
    tempArr.length = rightIndex + 1;
    tempArr.fill(0, 0, rightIndex + 1);

    let tempArrIndex = leftIndex;
    while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex){
        if(arr[leftAreaIndex] <= arr[rightAreaIndex]){
            tempArr[tempArrIndex] = arr[leftAreaIndex++];
        }else{
            tempArr[tempArrIndex] = arr[rightAreaIndex++];
        }
        tempArrIndex++;
    }

    if(leftAreaIndex > midIndex){
        for(let i = rightAreaIndex; i <= rightIndex; i++){
            tempArr[tempArrIndex++] = arr[i];
        }
    }else{
        for(let i = leftAreaIndex; i <= midIndex; i++){
            tempArr[tempArrIndex++] = arr[i];
        }
    }

    for(let i = leftIndex; i <= rightIndex; i++){
        arr[i] = tempArr[i];
    }
}

퀵 정렬 (Quick Sort)

기본 원리

1. 피벗 선택 : 주어진 배열에서 하나의 원소를 피벗(Pivot)으로 선택한다. 선택하는 방법에 따라 다양한 퀵 정렬의 변형이 존재한다.
2. 분할 : 피벗을 기준으로 배열을 두 부분으로 분할한다. 피벗보다 작은 원소들은 피벗의 왼쪽으로, 피벗보다 큰 원소들은 피벗의 오른쪽으로 이동한다. 피벗은 이 과정 후에 정렬된 위치에 있게 된다.
3. 재귀적 정렬 : 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열을 재귀적으로 정렬한다.

특징

• 평균 성능 : 평균적인 시간 복잡도는 θ(n log n)이다.
• 최악의 경우의 시간 복잡도는 O(n^2)이다.
• 선택된 피벗에 따라 성능이 크게 달라질 수 있으며, 피벗 선택 전략이 중요하다.
• 퀵 정렬이 병합 정렬보다 더 적은 메모리 공간을 차지한다.

구현

function quickSort(arr, left, right){
    if(left <= right){
        let pivot = divide(arr, left, right);
        console.log(right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

function divide(arr, left, right){
    let pivot = arr[left];
    let leftStartIndex = left + 1;
    let rightStartIndex = right;

    while(leftStartIndex <= rightStartIndex){
        while(leftStartIndex <= right && pivot >= arr[leftStartIndex]){
            leftStartIndex++;
        }

        while(rightStartIndex >= (left + 1) && pivot <= arr[rightStartIndex]){
            rightStartIndex--;
        }

        if(leftStartIndex <= rightStartIndex){
            swap(arr, leftStartIndex, rightStartIndex);
        }
    }

    swap(arr, left, rightStartIndex);
    return rightStartIndex;
}

function swap(arr, index1, index2){
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}