정렬 알고리즘 (n logn)

msg016·2022년 6월 12일
JavaScriptSortalgorithmstudy
0

CS Study

목록 보기
1/6
post-custom-banner

용어 정리

복잡도

알고리즘에서 복잡도는 시간복잡도와 공간복잡도로 나뉘어진다.

시간복잡도란 '문제를 해결하는 데 걸리는 시간과 입력의 함수 관계'를 말하며, 특정 알고리즘의 로직이 입력의 크기에 따라 얼마나 오랜 시간 소요되는지를 의미한다. 빅오 표기법이 주로 사용되며, 이러한 시간복잡도 표기를 통해 알고리즘이 수행되기 위해 필요한 연산의 횟수를 가늠하고, 성능의 지표로 활용할 수 있다.

공간복잡도는 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미하며, 시간복잡도와 동일하게 빅오 표기법으로 주로 표기한다.

빅오 표기법이란

간단히 말하면 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
예를 들어 N개의 입력 데이터가 존재하고, 어떤 알고리즘의 연산 횟수가 3N3+5N2+1,000,0003N^3 + 5N^2 + 1,000,000이라고 할 때, N이 증가함에 따라 N3N^3의 영향력은 급격히 증가하지만 나머지 항의 영향은 감소하기 때문에, 이를 간소화하여 O(N3)O(N^3)으로 표기한다.
그러나 N의 크기가 작다면 상수항의 영향력이 더 크기 때문에 표기법이 항상 절대적인 것은 아니며, 생략되는 항이 있기 때문에 빅오 표기법이 같은 알고리즘이라도 내부 로직 등에 따라 실제 수행되는 연산 횟수와 속도는 다를 수 있다.

다음은 주로 등장하는 시간 복잡도의 표이다.

빅오 표기법명칭
O(1)O(1)상수 시간(Constant time)
O(logN)O(logN)로그 시간(Log time)
O(N)O(N)선형 시간
O(NlogN)O(NlogN)로그 선형 시간
O(N2)O(N^2)이차 시간
O(2N)O(2^N)지수 시간

안정 정렬 (Stable Sort)

정렬은 순서의 유지 여부에 따라 두 가지로 나눌 수 있는데, 같은 값을 가지는 요소가 초기의 순서를 유지한다면 안정 정렬, 그렇지 않다면 불안정 정렬로 구분할 수 있다.
불안정 정렬에는 대표적으로 퀵 정렬, 힙 정렬 등이 있으며, 안정 정렬에는 버블 정렬, 삽입 정렬, 병합 정렬이 속한다. 후술할 병합 정렬과 삽입 정렬이 결합된 팀 정렬 또한 안정 정렬에 속한다.

참조 지역성의 원리 (Locality)

실행되기 전의 프로그램은 보조 기억장치(SSD, HDD)에 저장되어 있다가 실행되면 프로세스가 되어 주 기억장치(RAM)에 올라오게 된다. 이 때 프로세스는 Text Section, Data Section 등 여러 부분으로 나뉘어 각각 실행 코드, 전역 변수 등의 정보를 담게 된다.
CPU는 프로세스를 처리하며 프로세스 내부의 정보가 필요하면 주 기억장치에 접근하게 되는데, 일반적으로 CPU의 처리 속도가 RAM보다 현저히 빠르기 때문에 매번 기억장치로부터 정보를 읽어온다면 성능 저하가 발생하게 된다.
이를 해결하기 위해 CPU 내부 또는 외부에 용량은 적지만 속도가 빠른 저장공간을 마련하여 특정 관리 규칙에 따라 자주 참고하게 될지도 모르는 정보들을 CPU 근처에 보관하게 된다. 이러한 저장 공간을 캐시(Cache) 라고 하며, CPU는 어떤 정보를 필요로 할 때 우선적으로 캐시 메모리를 탐색하고 없다면 주 기억장치에서 가져오게 된다.
어떤 알고리즘을 수행하는 과정에서 이전에 참조한 값 또는 연관된 값에 반복적으로 접근하여 해당 정보를 주 기억장치가 아닌 캐시 메모리에서 주로 읽어온다면 이를 참조 지역성이 좋다고 표현하며, 보다 빠른 처리 속도를 보이게 된다.

병합 정렬 (Merge Sort)

병합정렬 또는 합병정렬은 분할 정복과 비교를 통한 정렬 알고리즘이다.

작동 과정

  1. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눈다.
  2. 정복(conquer): 나누어진 리스트를 재귀적으로 정렬한다.
  3. 결합(combine): 두 부분의 리스트를 다시 하나의 정렬 리스트로 합병하고 이 결과를 임시 배열에 저장한다.
  4. 복사(copy): 임시배열에 저장된 결과를 원래의 배열에 복사한다.

특징

  • 최선, 최악의 경우 모두 O(nlogn)O(nlogn)의 시간 복잡도를 가진다.
  • 인접 배열에 반복적으로 접근하기 때문에 어느정도의 참조 지역성을 만족한다.
  • 정렬 과정에서 원본 배열의 크기만큼의 추가 메모리를 필요로한다. (O(n)O(n)의 공간복잡도)

코드

JavaScript (오름차순 정렬)

function mergeSort(array, start = 0, end = array.length - 1) {
    if (start >= end) return;

    const middle = divide(array, start, end);
    merge(array, start, end, middle);
}

function divide(array, start, end) {
    const middle = Math.floor((start + end) / 2);

    mergeSort(array, start, middle);
    mergeSort(array, middle + 1, end);
    return middle;
}

function merge(array, start, end, middle) {
    const temp = [];
    let left = start;
    let right = middle + 1;

  	// conquer & combine
    while (left <= middle && right <= end) {
        if (array[left] > array[right]) temp.push(array[right++]);
        else temp.push(array[left++]);
    }

    while (left <= middle) {
        temp.push(array[left++]);
    }

    while (right <= end) {
        temp.push(array[right++]);
    }

    // copy
    for (let i = 0; i < temp.length; i++) {
        array[start + i] = temp[i];
    }
}

퀵 정렬 (Quick Sort)

퀵 정렬은 병합 정렬과 마찬가지로 분할 정복과 비교를 통한 정렬 알고리즘이다.

작동 과정

  1. 리스트의 중 하나의 원소를 pivot으로 선정한다.
  2. pivot의 앞에는 pivot보다 작은 원소들이 뒤에는 큰 원소들이 오도록 하고 pivot을 기준으로 두 개의 리스트로 나눈다.
  3. 분할된 리스트에서도 1번과 2번을 리스트 크기가 0 또는 1이 될 때까지 반복한다.

특징

  • 최선의 경우 O(nlogn)O(nlogn)의 시간 복잡도를, 최악의 경우 O(n2)O(n^2) 시간 복잡도를 가진다.
  • pivot의 값이 계속하여 분할 리스트의 최저 또는 최고값인 경우 최악의 경우를 나타낸다. 따라서 이미 정렬된 리스트 정렬에는 적합하지 않으며, 이를 극복하기 위해 pivot의 값을 랜덤으로 선정하거나 항상 정중앙에 위치한 값을 고르는 등의 변형이 가능하다.
  • pivot 인근의 데이터가 주로 스왑되기 때문에 참조 지역성이 좋다.

코드

JavaScript (오름차순 정렬, pivot값 중앙 선정)

function quickSort(array, start = 0, end = array.length - 1) {
    if (start >= end) return;

    const mid = Math.floor((start + end) / 2);
    const pivot = array[mid];
    let left = start + 1;
    let right = end;

    swap(array, start, mid);
    while (left <= right) {
        while (left <= end && array[left] <= pivot) {
            left++;
        }

        while (right > start && array[right] >= pivot) {
            right--;
        }

        if (left > right) {
            swap(array, start, right);
            break;
        } else {
            swap(array, left, right);
        }
    }

    quickSort(array, start, right - 1);
    quickSort(array, right + 1, end);
}

function swap(array, aIdx, bIdx) {
    const temp = array[aIdx];
    array[aIdx] = array[bIdx];
    array[bIdx] = temp;
}

힙 정렬 (Heap Sort)

힙 정렬은 주어진 배열을 힙 자료구조의 특징을 만족하도록 하는 Heapify 과정을 반복하여 정렬하는 방법이다.

작동 과정

1 - 1. i 번째 값을 (i * 2 + 1) 번째 값과 비교하여 더 작다면/크다면 교환한다.
1 - 2. i 번째 값을 (i * 2 + 2) 번째 값과 비교하여 더 작다면/크다면 교환한다.
2. 배열의 모든 원소에 대하여 수행한다.

특징

  • 추가적인 메모리 사용이 필요하지 않다. (Heapify 정렬의 경우)
  • 최선과 최악의 경우 모두 O(nlogn)O(nlogn)의 시간 복잡도를 가진다.
  • 불안정 정렬이며, 배열의 넓은 범위에 접근하게 되므로 참조 지역성이 좋지 못하다.

코드

JavaScript (최소 힙)

function heapSort(array) {
    // 초기 최대 힙 구현.
    for (let i = array.length - 1; i >= 0; i--) {
        heapify(array, array.length - 1, i);
    }

    // 최대의 크기를 가진 루트 노드를 리프 노드로 옮긴 뒤, 갱신된 위치를 제외하고 다시 최대 힙 구현.
    for (let i = array.length - 1; i >= 1; i--) {
        swap(array, 0, i);
        heapify(array, i - 1);
    }
}

function heapify(array, length, idx = 0) {
    while (true) {
        const leftChild = idx * 2 + 1;
        const rightChild = idx * 2 + 2;

        if (length >= rightChild) {
            // 자식 노드가 두 개일 경우 더 큰 노드와 비교 (최대 힙)
            const maxChild = (array[leftChild] < array[rightChild]) ? rightChild : leftChild;
            if (array[idx] < array[maxChild]) {
                swap(array, idx, maxChild);
                idx = maxChild;
            } else {
                break;
            }
        } else if (length === leftChild) {
            // 자식 노드가 하나인 경우 해당 자식과 비교.
            if (array[idx] < array[leftChild]) {
                swap(array, idx, leftChild);
            } else {
                break;
            }
        } else {
            // 리프 노드라면 정렬 종료.
            break;
        }
    }
}

function swap(array, aIdx, bIdx) {
    const temp = array[aIdx];
    array[aIdx] = array[bIdx];
    array[bIdx] = temp;
}

팀 정렬 (Tim Sort)

팀 정렬은 병합 정렬과 삽입 정렬이 조합된 하이브리드 정렬 알고리즘이다.
삽입 정렬은 기본적으로 O(n2)O(n^2)의 시간 복잡도를 가지는 정렬 알고리즘이지만, 인접 메모리와의 반복 비교를 통한 정렬 방식으로 참조 지역성을 매우 잘 만족한다. 때문에 시간 복잡도 표기에서 생략되어 있는 상수 CC를 고려하여 다른 O(nlogn)O(nlogn)의 알고리즘(Quick sort)와 비교해보면, nn의 값이 작을 경우 상수 CC가 더 작은 삽입 정렬의 경우가 유리하다는 아이디어에 기반한다.

작동 과정

  1. 본래의 배열을 Run이라고 불리는 작은 블록으로 분할한다.
    이 때 2개씩 합치는 병합 정렬의 특성을 고려하여, Run의 크기는 원래 배열의 사이즈에 따라 총 Run의 개수가 2의 제곱수가 되도록 32 ~ 64 사이로 다양하게 결정된다.
  2. Runs들을 삽입 정렬을 통해 정렬한다.
  3. 인접한 Runs를 병합 정렬을 통해 정렬한다.

최적화

  • Run
    하나의 Run의 크기가 커질 수록 그 길이만큼의 병합 과정이 생략되기 때문에 더 높은 성능을 기대할 수 있다. 이를 위해 초기 두 개의 원소를 비교하여 오름차순 또는 내림차순을 결정한 뒤, 2x2^x 크기가 될 때까지 삽입정렬을 수행한다. 그 다음, 이후의 원소가 계속해서 정렬 기준을 만족할 경우 Run에 포함시킨다. 이후 내림차순으로 정렬된 Run은 뒤집어 오름차순으로 변환한다.
    tim-sort-optimization-run

  • Binary Insertion sort
    Run을 생성할 때 앞의 원소들은 이미 정렬되어 있다는 전제를 기반으로 이분탐색을 통해 원소를 삽입할 위치를 찾는다. O(n)O(n)의 비교 대신 O(logn)O(logn)의 비교를 통해 시간 절약을 기대할 수 있다.

  • Merge
    앞서 minRun까지의 삽입정렬 후 추가적인 병합을 통해 만들어진 각각의 Run들은 크기가 제각각으로 효율적인 병합 정렬을 위해 최대한 비슷한 크기의 덩어리끼리 병합되도록 조정한다.
    병합되어야 할 Run들의 스택 상위 3개의 A, B, C Run이 있다고 할 때, 다음과 같은 조건을 확인한 뒤, 만족하지 않을 경우 중간 Run인 B를 A와 C 중 더 작은 Run과 병합한다.

    • |C| > |B| + |A|
    • |B| > |A|

    또한 병합되는 배열의 크기인 NN만큼의 추가 메모리를 필요로하는 병합 정렬의 특징을 해결하기 위해 두 Run 중 작은 Run을 복사한 뒤, 각 Run의 시작부분부터 병합정렬을 수행한다. 이 경우, 최대 N/2N/2의 추가 메모리로도 병합을 진행할 수 있다.

  • Galloping

    Galloping 동작 과정 from Naver D2

    병합을 진행하는 과정에서 MIN_GALLOP번 연속으로 한 Run에서만 병합이 이뤄질 경우, $2^k$만큼 뛰어 넘으며 대소비교를 진행 후, 이분 탐색을 통해 삽입 위치를 결정한다. 이후 하나의 Run에서 연속적으로 병합되지 않으면 다시 하나씩 비교하며, 실 사용에서는 Galloping이 반복될 경우 MIN_GALLOP이 감소하고 반대의 경우 증가하는 등의 보다 효율적으로 동작하게 된다.

자바스크립트의 정렬

자바스크립트의 Array.prototype.sort() 메소드는 각 엔진이 어떻게 구현했는지에 따라 사용되는 정렬 알고리즘이 다르다. 그러나 ECMA2019에서 안정 정렬을 보장하게 되어, 인터넷 익스플로러를 제외한 모든 브라우저에서 Array.prototype.sort()는 안정 정렬로 동작하게 되었다.
크롬 브라우저의 V8 엔진은 Tim sort를 사용하고 있으며, 파이어폭스 브라우저의 SpiderMonkey 엔진은 Merge sort를 사용하고 있다.

profile
msg016
프론트엔드 개발자 지망생
다음 포스트

운영체제 기본개념 & 인터럽트

post-custom-banner

0개의 댓글