Quick Sort, Merge Sort, and Locality

2021. 2. 2. 02:16

학교 수업시간들에서 흔하게 배울수 있는 Sorting 에는 Selection, Bubble, Insertion 등의 n² 의 시간복잡도를 가지는 정렬과 Quick sort와 Merge sort같이 nlogn의 시간복잡도를 가지는 대표적인 정렬 방법이 있다.

인터넷 블로그들을 떠돌다가, 일반적으로 Quick sort가 Merge sort보다 크다는 정보를 접하였다.

하지만 대게 알려지기로는 Quick sort는 피봇의 선정에 따라 최악의 경우 n² 의 시간복잡도를 보여줄 여지도 있다.

이러한 Quick sort가 Merge sort보다 대게 성능이 좋은 이유는 Locality와 관련이 있다고 한다. Locality의 개념을 알아보고 왜 Quick sort가 더 빠른지 알아보도록 하자.

1. Quick Sort and Merge Sort

int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; 
    int low = left + 1;
    int high = right;
 
    while (low <= high) 
    {
        while (low <= right && pivot >= arr[low])
        {
            low++; 
        }
        while (high >= (left+1)  && pivot <= arr[high]) 
        {
            high--;
        }
        if (low <= high)
        {
            Swap(arr, low, high);
        }
    }
    Swap(arr, left, high);
    return high; 
 
}
 
void QuickSort(int arr[], int left, int right)
{
    if (left <= right)
    {
        int pivot = Partition(arr, left, right);
        QuickSort(arr, left, pivot - 1); 
        QuickSort(arr, pivot + 1, right); 
    }
}

위는 일반적인 Quick Sort 코드이다.

이 퀵정렬에서는 다른 정렬법과는 다르게 pivot을 사용한다.

코드상에서 while문을 통해 pivot값을 기준으로 큰값과 작은값을 좌우로 나누는것을 알수있다. 그후 재귀적으로 다시 나뉜 부분또한 pivot을 설정해 정렬을 수행한다.

퀵정렬의 느낌은 한마디로 큰 그룹에서부터 작은 그룹으로 연산이 진행되는 Top-Down 방식이라 할 수 있다.

눈여겨 보아야 할 것은 별도의 메모리가 필요하지 않다. 위코드 내에서도 단지 arr배열 내에서 정렬이 수행된다.

void mergeSort(int data[], int p, int r) {
    int q;
    if(p<r) {
        q = (p+r)/2;
        mergeSort(data, p , q);
        mergeSort(data, q+1, r);
        merge(data, p, q, r);
    }
}
void merge(int data[], int p, int q, int r) {
    int i = p, j = q+1, k = p;
    int tmp[8]; 
    while(i<=q && j<=r) {
        if(data[i] <= data[j]) tmp[k++] = data[i++];
        else tmp[k++] = data[j++];
    }
    while(i<=q) tmp[k++] = data[i++];
    while(j<=r) tmp[k++] = data[j++];
    for(int a = p; a<=r; a++) data[a] = tmp[a];
}

다음으로 위는 Merge Sort이다.

이 합병 정렬의 경우 일단 각각으로 다 쪼개어 작은 그룹을 정렬한 후 더 큰 그룹으로 합쳐나가는 Bottom-Up 방식이다.

이러한 과정에서 데이터들을 임시적으로 저장하는 temp배열이 필요하다.

2. 참조의 지역성(Locality of Refrence)과 메모리

학부 운영체제 수업을 듣다보면 지역성의 원리라는 단어에 대해 듣게 된다.

이러한 지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다. 메모리 내의 정보를 균일하게 엑세스 하는게 아닌, 짧은 시간내에 특정 부분을 집중적으로 참조하는 특성이다.

이러한 지역성의 원리를 설명할때 가장 자주등장하는게 메모리 계층인데, 결론적으로 가장 속도가 빠른 레지스터는

하위계층들까지의 접근을 대신해 데이터를 가지게 되는데, 이 작업을 캐싱(Caching)이라 하고, 이전에 사용한 데이터가

다시 사용될것을 예측하고 시기적절하게 상위 계층 메모리에 갖다놓는것이다.

이때 다음 아래의 두가지 원리를 통해 해결할 수 있다.

시간적 지역성(Temporal Locality) : 최근 접근된 내용이 또 다시 접근될 확률이 높다.
공간적 지역성(Spatial Locality) : 한 지역의 내용이 접근되었다면, 그 주위의 내용도 접근될 확률이 높다.

그렇다면 왜 Locality가 정렬 알고리즘의 평가 기준이 될 수 있을까?

3. Quick Sort, Merge Sort, and Locality of Refrence

정렬하려고 하는 데이터들이 다른 페이지로 이동하는 것 없이, 자신의 페이지에서 계속 있는게 좋다. 다른 캐쉬에 없는 페이지로 이동하면 page cache hit 비율이 떨어지게 된다.

그래서 결국 physical memory로 접근을 해야 하기 때문에 시간이 상대적으로 오래 걸린다.

만약 자신의 페이지에 계속 있는다면, cache에서 반복적으로 접근하기 때문에 시간이 덜 걸린다. 결국 데이터가 이동하지 않을 수록 좋다.

위 코드에서 알수 있듯이 Quick Sort는 Merge Sort에 비해 pivot에 의한 분할은 했지만 데이터가 존재하는 위치는 변하지 않는다. 따라서 제자리정렬이라 할수있으며 지역성의 원리에 따라 더 빠른 성능을 보이기도 한다는 것이다.

Merge Sort

Quick Sort

#Reference

https://medium.com/pocs/locality%EC%9D%98-%EA%B4%80%EC%A0%90%EC%97%90%EC%84%9C-quick-sort%EA%B0%80-merge-sort%EB%B3%B4%EB%8B%A4-%EB%B9%A0%EB%A5%B8-%EC%9D%B4%EC%9C%A0-824798181693

https://velog.io/@agugu95/%EC%B0%B8%EC%A1%B0%EC%9D%98-%EC%A7%80%EC%97%AD%EC%84%B1%EA%B3%BC-Quicksort-vs-Mergesort

'Algorithm' 카테고리의 다른 글

Dynamic Programming(1) (0)	2021.02.02

기억보단 기록을