[CS & Algorithm] 정렬 알고리즘

정렬 (Sort)

선택 정렬 (Selection Sort)

• 매 단계에서 가장 작은 원소를 선택해 앞으로 보내는 정렬 방법
• 시간 복잡도 O(N^2)로 비효율적인 정렬 알고리즘 중 하나이다.
• 외우지 않아도 구현할 수 있을 정도로 쉽게 구현이 가능하다.

function selectionSort(arr){
    for(let i = 0; i < arr.length; i++)
    {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++)
        {
            if (arr[minIndex] > arr[j]){
                minInedx = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
} // 선택 정렬

버블 정렬 (Bubble Sort)

• 인접한 두 원소를 확인하여 위치를 서로 변경한다.
• 시간 복잡도 O(N^2)로 비효율적인 정렬 알고리즘 중 하나이다.
• 선택 정렬보다 비효율적인 알고리즘이다.

function bubbleSort(arr){
    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 tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }        
        }
    }
} // 버블 정렬

삽입 정렬 (Insertion Sort)

• 각 숫자를 적절한 위치에 삽입하는 정렬
• 시간 복잡도는 O(N^2)이다.
• 버블, 선택보다 빠르고 정렬이 되어 있는 경우는 빠르게(O(N)) 동작한다.

function insertionSort(arr){
    for(let i = 1; i < arr.length; i++)
    {
        for(let j = i; j > 0; j--){
            if(arr[j] < arr[j - 1])
            {
                let temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
            else
                break;
        }
    }
} //삽입 정렬

병합 정렬 (Merge Sort)

• 분할 정복 (divide and conquer) 알고리즘 정렬
• 시간 복잡도 O(NlogN)을 보장한다.

분할 정복이란 3가지 프로세스로 나눌 수 있다.

1. 분할 : 큰 문제를 작은 부분 문제로 분할
2. 정복 : 작은 부분 문제를 각각 해결
3. 조합 : 해결한 부분 문제의 답을 이용해 다시 큰 문제 해결

• 일반적으로 분할하는 방식이 동일한 경우가 많기 때문에 더 이상 분할 할 수 없을 때까지 분할하기 좋은 재귀 함수를 사용한다.
• 단점 : 재귀 함수를 사용하는 것은 오버헤드 발생 확률이 높아진다.

function merge(arr, left, mid, right){
    let i = left;
    let j = mid + 1;
    let k = left;
    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
        else sorted[k++] = arr[j++];
    }
    if (i > mid)
    {
        for (; j<=right;j++) sorted[k++] = arr[j];
    }
    else {
        for (; i <= mid; i++) sorted[k++] = arr[i];
    }
    for (let x = left; x <= right; x++)
    { arr[x] = sorted[x]};
}

function mergeSort(arr, left, right)
{
    if (left < right)
    {
        let mid = parseInt((left + right) / 2);
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

JS 정렬 라이브러리

• 위에 설명된 정렬은 모두 기본 제공 라이브러리에서 사용할 수 있다.
• sort() 함수는 O(NlogN)을 보장한다.
• sort() 함수의 매개변수는 함수이다.

arr.sort((a, b) => a-b) // 오름차순
arr.sort((a, b) => b-a) // 내림차순

arr.sort() //문자열 정렬 (오름차순)

//문자열 대소문자 구분하고 싶지 않을 경우
function compare(a, b){
  let caseA = a.toUpperCase();
  let caseB = b.toUpperCase();
  if (caseA < caseB) return -1;
  else if (caseB > caseA) return 1;
  else return 0;
}

arr.sort(compare);