Written by JS970
on March 20, 2023

컴퓨터 알고리즘 2023-03-20 수업정리

Flow

Divide and Conquer - Quicksort

Divide and Conquer - Quicksort

Quicksort Algorithm(퀵 정렬)

배열은 재귀적으로 두 개의 partition으로 나눠진다.(Divide)
- 배열은 pivot값을 기준으로 pivot값보다 작은 partition, pivot값보다 크거나 같은partition의 두 개의 sub-arrays로 나눠진다.
나눠진 두 개의 partition배열에 대해서 정렬이 이루어진다.(Conquer)
Merge Sort와 달리 별도의 메모리 공간을 필요로 하지 않는다.
- 새롭게 배열을 생성하지는 않기 때문

Worst-case Complexity of Quicksort

초기 배열의 원소들이 얼마나 균등하게 분포되어 있는지에 따라 시간복잡도가 다르다. 특히, pivot value에 따라 시간복잡도가 달라진다.
이미 배열이 정렬되어 있지만 이 상태를 모른 채 Quicksort를 수행하는 경우가 가장 많은 연산을 해야 하는 worst-case이다.
- n개의 원소가 있는 배열에서 comparison연산이 가장 많이 일어나는 경우, n-1번의 연산과 다시 n-1개의 원소를 가지는 배열에 대한 Quicksort 연산을 거쳐야 한다. $$T(n) = T(n-1) + (n-1)$$
- 모든 경우에 대해 위와 같은 최대 연산을 가지게 된다면 아래와 같은 시간복잡도를 가지게 된다. $$T(n) = \sum^{n}_{k=1}(k-1) \in \Theta(n^2)$$

Average-case time complexity of Quicksort

n개의 서로 다른 원소를 가지는 배열에서 Mn = total comparison이라고 하자. $$M_n = \sum_{j=1}^n(n-1 + M_{j-1} + M_{n-j})\frac{1}{n}$$ $$M_n =n-1 + \frac{2}{n}\sum_{k=1}^{n-1}M_k$$ $$nM_n = n(n-1)+2\sum_{k=1}^{n-1}\ \ ...\ (1)$$ 이렇게 얻어진 식의 n에 n+1을 대입하면$$(n+1)M_{n+1} = n(n+1) + 2\sum_{k=1}^{n}M_k\ \ \ ...\ (2)$$(2) - (1)을 하면$$(n+1)M_{n+1} = (n+2)M_n+2n$$$$\frac{M_{n+1}}{n+2} = \frac{M_n}{n+1}+\frac{2n}{(n+1)(n+2)}$$ $$\frac{M_{n+1}}{n+2} = \frac{M_{n-1}}{n} + \frac{2(n-1)}{n(n+1)} +\frac{2n}{(n+1)(n+2)} = 2 \sum_{k=0}^{n-1}\frac{n-k}{(n+1-k)(n+2-k)}$$ n-k를 i로 치환하면$$M_{n+1} = 2(n+2)\sum_{k=0}^{n-1}\frac{n-k}{(n+1-k)(n+2-k)} = 2(n+2)\sum_{i=1}^{n}\frac{i}{(i+1)(i+2)}$$ 부분분수로 분리하면$$M_{n+1} = 2(n+2)\sum_{i=1}^n[\frac{2}{i+2}-\frac{1}{i+1}]$$ Average-case에 대해 Time complexity를 고려중이다. 분포는 균일분포이며, 이때의 평균값을 Average-case라 말할 수 있으므로 정적분을 취해 계산을 이어갈 수 있다.$$M_{n+1} = 2(n+2)[\int_3^{n+2}\frac{2}{x}dx - \int_2^{n+1}\frac{1}{x}dx] = 2(n+2)[2log(n+2) - log(n+1) + log2 - 2log3]$$ $$M_{n+1} = 2(n+2)[log(n+2) + log(\frac{n+2}{n+1}) + log2 - 2log3]$$

따라서 Quicksort Algorithm의 Average-Case Time Complexity는 다음과 깉이 말할 수 있다. $$M_n \in \Theta(nlogn)$$

Implementataion

다음은 quicksort algorithm의 c++ 구현이다.

#include <iostream>
using namespace std;
 
int partition(int arr[], int pivot, int first, int last)
{
    int pivotIndex = first++;
    while(first <= last)
    {
        if(arr[first] > pivot && arr[last] <= pivot)
        {
            int tmp = arr[first];
            arr[first] = arr[last];
            arr[last] = tmp;
        }
 
        if(arr[first] <= pivot) first++;
        if(arr[last] > pivot) last--;
    }
 
    return last;
}
 
void quickSort(int arr[], int first, int last)
{
    if(first < last)
    {
        int pivot = arr[first];
        int splitPoint = partition(arr, pivot, first, last);
 
        arr[first] = arr[splitPoint];
        arr[splitPoint] = pivot;
 
        quickSort(arr, first, splitPoint-1);
        quickSort(arr, splitPoint+1, last);
    }
}
 
int main()
{
    int arrSize; cin >> arrSize;
 
    int * arr = new int[arrSize];
    for(int i = 0; i < arrSize; i++)
        cin >> arr[i];
 
    quickSort(arr, 0, arrSize-1);
 
    for(int i = 0; i < arrSize; i++)
        cout << arr[i] << " ";
    cout << endl;
 
    return 0;
}

Top