알고리즘 - Quick(퀵) vs Merge(병합) 정렬(+TCO, 참조 지역성)

 

해당 포스팅은 표준(Standard)적인 퀵 / 병합 정렬의 경우에 대해 설명합니다.

각 정렬 방식의 응용에 따라 다양한 Variation이 있는 부분은 감안하지 않았습니다.

 

퀵 정렬과 병합 정렬 차이

 

우선 기본적으로 퀵 / 병합 정렬이 무엇인지 다시 한 번 간단히 알아보자.(관련 포스팅은 여기 → 퀵 / 병합)

 

귀찮은 분들을 위해 간단히 코드는 아래의 접힌 글에 써놓았다.

1) 퀵 정렬

public class QuickSort{
    public static void main(String[] args){
        int[] arr = new int[100];
        for(int i=0; i < arr.length; i++){
            arr[i] = (int)(Math.random() * 100);
        }
        
        quickSort(arr, 0, arr.length);
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
    }

    private static void quickSort(int[] arr, int start, int end){
        if(end - start < 2){
            return;
        }
        int pivotIndex = partition(arr, start, end);

        quickSort(arr, start, pivotIndex);
        quickSort(arr, pivotIndex+1, end);
    }

    private static int partition(int[] arr, int start, int end){
        int pivot = arr[start];
        int i = start;
        int j = end;

        while(i < j){
            while(i < j && arr[--j] > pivot);
            while(i < j && arr[++i] < pivot);

            if(i < j){
                swap(arr, i, j);
            }
        }
        swap(arr, start, j);
        return j;
    }

    private static void swap(int[] arr, int l, int r){
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}

 

2) 병합 정렬

public class MergeSort{
    public static void main(String[] args){
        int[] arr = new int[100];
        for(int i=0; i < arr.length; i++){
            arr[i] = (int)(Math.random() * 100);
        }
        
        mergeSort(arr, 0, arr.length-1);
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
    }
    
    public static void mergeSort(int[] arr, int start, int end){
        if(start == end) return;
        
        int mid = (start+end)/2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid+1, end);
        
        int[] temp = new int[end-start+1];
        int idx = 0;
        int left = start;
        int right = mid+1;
        while(left <= mid && right <= end){
            temp[idx++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
        }
        while(left <= mid){
            temp[idx++] = arr[left++];
        }
        while(right <= end){
            temp[idx++] = arr[right++];
        }
        for(int i=start; i <= end; i++){
            arr[i] = temp[i-start];
        }
    }
}

 

이 2가지 알고리즘은 동일하게 분할정복(Divide and Conquer) 방식의 알고리즘을 이용해 비슷하지만 다른 방식으로 정렬을 수행한다. 따라서 이 2가지를 비교해보자.

그러면 아래 표와 같이 퀵, 병합 정렬의 차이를 표로 알아보자.

구분	퀵 정렬	병합 정렬
부분 배열의 구획	나뉘어진 배열은 여러 비율로 나뉜다.	배열은 항상 반으로 나뉜다.
최악의 경우 시간복잡도	$O(n^2)$	$O(nlogn)$
사용 용도	작은 크기의 배열에서 잘 동작	어떤 크기의 Dataset에서도 적절히 동작
효율성	작은 크기 Dataset에서는 병합 정렬보다 빠르다.	큰 Dataset에서는 퀵 정렬보다 빠르다.
정렬 방식	내부 정렬	외부 정렬
별도 저장 공간	불 필요	필요
참조 지역성	좋음	퀵 정렬 대비 나쁨
Stable	X(그러나 구현 방식에 따라 가능)	O

 

 

퀵 정렬  - 배열 / 병합 정렬 - 연결리스트 ?

 

다음의 내용과 같이 정리할 수 있다.

퀵 정렬은 배열에, 병합 정렬은 연결리스트에 더 선호되는 경향이 있다.
  → 연결리스트는 메모리 공간 할당 시에, 배열과 달리 상호 노드가 인접하여 공간이 할당되지 않을 수 있다.(지역성 설명에서 보충)

퀵 정렬은 Cache에 더 Friendly 하다. 즉, 참조 지역성에 더욱 효과적이다.(배열인 경우 더욱 효과적)
퀵 정렬은 Tail recursive 하여, Tail Call Optimization이 적용되므로 메모리 공간 사용을 더욱 최적화 한다.

병합 정렬은 추가 필요 저장 공간이 필요해, 추가 공간 할당/해제에 시간이 더 소요된다.
병합 정렬은 연결리스트의 경우 정렬 시에 상호 pointer만 변경하면 되므로 추가 공간이 필요한 단점이 보완된다.(추가 공간 불필요)
병합 정렬은 정렬 시, 순차 탐색을 하며 퀵 정렬은 Random 탐색을 하는 경우가 많아, 연결리스트는 퀵 정렬이 불리하다.
  → 이 부분이 이해가 안되면 연결리스트 내용 참조
  → 간단히 설명하면, Random 탐색 시, 해당 위치의 노드를 찾기 위해 순차적으로 탐색해야 하기 때문에 그 시간이 소요됨!

데이터 크기가 크면 퀵 정렬보다는 병합 정렬이 선호될 수 있다.
  → 데이터 크기가 크면 메모리 공간의 사용에 영향도 있으나, 최악의 경우에 퀵 정렬은 $O(n^2)$이 소요된다.
  → 반면 병합 정렬은, 데이터 크기에 무관하게 일관된 속도를 유지한다.

 

지금부터 일부 내용에 대해 알아보자.

 

참조 지역성(Locality)

지역성(Locality)는 CPU가 짧은 시간 범위 내 일정 구간 메모리 영역을 반복적 엑세스하는 경향을 의미한다.

CPU는 메모리의 각 위치에서 현재 실행중인 프로그램의 값들을 가져오는데 그 내용이 메모리에 없으면 디스크 저장장치로 접근하여 파일 일부를 메모리로 Load 시켜야 한다.

만약 이미 메모리에 이미 올라와 있다면 그것을 Hit했다고 하고 이 Hit율이 높다면 전체적인 성능이 더욱 빠르게 동작하게 된다.

 

이 성능을 위해 메모리는 지역성의 원리를 이용해 페이지를 적재하도록 설계되어 있다. 지역성은 3가지로 나뉜다.

① 시간(Temporal) 지역성 : 최근 사용된 Page를 다시 참조할 확률이 높다
② 공간(Spatial) 지역성 : 최근 사용된 Page의 근처 Page들이 다시 참조될 확률이 높다.
③ 순차(Sequential) 지역성 : 데이터가 순차적으로 접근되는 경향으로 프로그램 명령어가 순차적으로 구성되어 있는 경우이다.

 

이 개념을 캐시로 확장하면, 자주 사용되는 Page는 물리 메모리에만이 아니라 캐시에도 두는데, 지역성의 원리에 따라 Hit율이 높다면 캐시에 해당 Page를 자주 접근하게 되어 훨씬 성능이 올라가게 되는 것이다.

 

이 지역성의 원리에 따라, 퀵 정렬은 병합 정렬 대비 더 빠르게 주변 데이터에 접근하므로 속도가 일반적으로 더 빠르다.
이를 애니메이션으로 알아보자.

병합 정렬 부터 알아보자.

퀵 정렬을 알아보자.

 

위의 그림을 통해 보면, 병합 정렬은 좌우의 양쪽 끝의 데이터를 지속적으로 반복하여 접근하고 있다. 이것이 의미하는 바는 캐시 메모리의 Page가 계속 변경될 수 있다는 것이다.

반면에 퀵 정렬은 데이터 정렬이 초반을 제외하고는 넓은 범위에서 움직이지 않으므로 한정적인 캐시 메모리 Page에 좀 더 자주 빠르게 접근하여 Page 변경이 상대적으로 덜 일어난다.

 

즉, 퀵 정렬은 HW 적으로 더욱 빠르고 효율적인 방법이라는 것이다.

 

 

Tail recursion

우선 여러가지 다른 개념을 먼저 알아보자!

 

① Tail Call

이것은 현재 어떤 함수(메소드)가 실행될 때, return 명령어를 만나기 전에 특정 함수가 호출되는 것을 의미한다.

해당 함수가 호출될 때, 마지막으로 수행되어 현재 함수(메소드)의 스택 프레임의 할당 해제가 일어나기 직전에 수행되는 경우를 의미한다.

return function(--n) // 이것은 Tail Call, 함수의 실행이 마지막!
return function(n--) // 이것은 Non-Tail Call, 함수 실행 후 -- 연산 추가 실행!

 

② Tail recursion

Tail Call의 특수한 경우로 재귀 호출이 현재 함수(메소드)에서 마지막으로 수행되는 경우를 의미한다. 다음을 보자.

static void function(int n){
   ...
   return function(--n);  // 재귀적으로 Tail Call을 수행중!
}

 

③ TCO(Tail Call Optimization)

Tail Call을 최적화하는 것을 말하며 Compiler에서 지원되는 부분으로, 지원 되지 않는 언어, 브라우저 등이 있다.

마지막 호출에서 Tail Call을 하면 새 스택 프레임 생성을 반복하지 않고 같은 스택 프레임에서 다시 호출되는 함수의 진입점으로 GoTo하여 루틴을 진행할 수 있는 것을 의미한다.

 

스택 프레임(Stack Frame)은 함수 호출 시, 메모리 스택(Stack)에는 함수 매개변수, 반환 주소값, 지역 변수 등이 저장되는데 이러한 스택 영역 저장되는 정보를 스택 프레임이라고 한다.

이것이 있기 때문에, 함수가 호출되기 이전 상태로 돌아가는 것이 가능하다. 아래 그림을 보자.

출처 : http://tcpschool.com/c/c_memory_stackframe

 

Tail Call Optimization(최적화)는 언어의 Compiler에서 지원하여 현재 스택 프레임의 값만 대체해서 별도 공간을 할당하지 않고 재사용하도록 최적화를 하는 것이다.

그 중에서도 Tail Call이 Tail recursion(재귀) 형태로 동작하고 최적화를 하면 그것을 언어 실행환경(컴파일러)에서 Tail recursion elimination이 적용된다고 부른다.

아래 코드를 보자.(C++ 코드인데, 자바는 TCO를 지원하지 않는 것으로 알고 있어 C++로 코드를 썼다.)

// Tail recursive 함수 구현
void print(int n) {
    if (n < 0) 
       return;
    cout << " " << n;
    print(n-1); // Tail recursion 함수 호출
}

// Tail recursion elimination 적용 되어 Compiler가 최적화 하는 법
static void print(int n) {
start:
    if (n < 0)
       return;
    cout << " " << n;
 
    // 재귀 호출의 매개변수를 업데이트하고
    // goto를 통해 start로 바로 재귀호출을 대체하여 별도 스택 프레임을 생성하지 않음!
    n = n-1
    goto start;
}

 

④ 퀵 정렬에서의 TCO

퀵 정렬은 이미 Tail recursive 하다. 아래의 내용을 보자.

 

// C++ 코드로 작성된 2회의 재귀 호출을 통해 내부 정렬을 수행하는 퀵 정렬 메소드
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);  // partition은 생략
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

// Tail Call Elimination이 진행되어 내부적으로 변경되는 모습
void quickSort(int arr[], int low, int high) {
    start:
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        
        low = pi+1;
        high = high;
        goto start;  // Parameter 값을 변경하고 내부 정렬 수행하도록 제어문을 사용
    }
}

 

위 코드에서 보다 시피, 마지막에 수행되는 quickSort(매개변수)의 재귀 호출은 Tail Call Elimination이 수행된 것이다. 이를 통해 추가적인 스택 프레임이 없이 더 효율적으로 수행될 수 있다.

 

반면 병합 정렬은 Tail recursive 하지 않아 메모리 공간 활용이 상대적으로 비 효율적이다.

 

 

긴 내용 읽어주셔서 감사합니다.

오류가 있으면 코멘트 주시면 수정하겠습니다.