Merge / Quick / Heap Sort (Medium)

출처(위키피디아/GeeksforGeeks)

1. Merge Sort(병합 정렬)

- 분할 정복 알고리즘.

- 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (원소가 하나인 리스트는 정렬된 것과 같으므로)

- 부분 리스트가 하나만 남을때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 

- 마지막 남은 부분리스트가 정렬된 리스트이다.

- Stable / Not in place

최악 시간복잡도	Θ( n log n )
최선 시간복잡도	Θ( n log n )
평균 시간복잡도	Θ( n log n )
공간 복잡도	Θ( n )

void merge(int arr[], int l, int m, int r){
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];

    for(int i=0; i<n1; i++)
        L[i] = arr[l+i];
    for(int i=0; i<n2; i++)
        R[i] = arr[m+1+i];
    
    int i = 0;
    int j = 0;
    int k = l;

    while( i < n1 && j < n2){
        if(L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
        
    while(i < n1){
        arr[k++] = L[i++];
    }
    
    while(j < n2){
        arr[k++] = R[j++];
    }
}

// Top-Down
void mergeSort(int arr[], int l, int r){
    if (l<r){
        int m = (l+r-1)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr,l,m,r);
    }
}

// Bottom-Up
void mergeSortIterative(int arr[], int l, int r){

    for(int m=1; m<=r-l; m=2*m){
        // m = 1, i = 0, 2, 4, 6, 8...
        // m = 2, i = 0, 4, 8...
        // m = 4, i = 0, 8...
        for(int i=l; i<r; i+=2*m){
            int start = i;
            int mid = i + m - 1;
            int end = min(i + 2*m - 1, r);
            merge(arr, start, mid, end);
        }    
    }
}

2. Quick Sort(퀵 정렬)

- 리스트 가운데서 하나의 원소(피벗)를 구한다.

      1. 첫 번째 원소를 선택

      2. 마지막 원소를 선택 (이미 정렬된 입력에 대해 Θ( n ^ 2 ))

      3. 랜덤 원소를 선택

      4. 중간 원소를 선택

- 피벗 앞에는 피벗보다 값이 작은 원소들이 오고, 뒤에는 피벗보다 값이 큰 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나누다. (Partition)

- 분리된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트이 크기가 0이나 1일 될때까지 반복된다.

- Unstable / In-place

최악 시간복잡도	Θ( n ^ 2 )
최선 시간복잡도	Θ( n log n )
평균 시간복잡도	Θ( n log n )
공간 복잡도	Θ( log n )

inline void swap(int &a, int &b){
    int t = a; a = b; b = t;
}

int partition(int arr[], int low, int high){
    int &pivot = arr[high];
    int i = low - 1;

    for(int j=low; j < high; j++){
    	// If current element is smaller than the poivot
        if(arr[j] < pivot)
            swap(arr[++i], arr[j]);
    }
    swap(arr[++i], pivot);
    return  i;
}

void quickSort(int arr[], int low, int high){
    if(low < high){
    	// pi is partioning index, arr[p] is now at right place
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

void quickSortIterative(int arr[], int low, int high){
    // create auxiliary stack
    int stack[high - low + 1];
    // initialize top of stack
    int top = -1;

    // push initial low and high to stack
    stack[++top] = low;
    stack[++top] = high;
    
    while(top >= 0){
        // pop high and low
        high = stack[top--];
        low = stack[top--];

        // Set pivot element at its correct position in sorted array
        int p = partition(arr, low, high);

        // If there are elements on left side of pivot
        if(p - 1 > low){
            // then push left side to stack
            stack[++top] = low;
            stack[++top] = p - 1;
        }

        // If ther are elements on right sidf of pivot
        if(p + 1 < high){
            // then push right side to stack
            stack[++top] = p + 1;
            stack[++top] = high;
        }
    }
}

 

3. Heap Sort(힙 정렬) 

- 최대 힙 or 최소 힙 트리를 구성해 정렬을 하는 방법으로 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

- 입력에 대해 최대 힙을 구성한다.

- 가장 큰 수(루트에 위치)를 힙의 마지막 항목과 교체하고 힙의 크기를 1 줄인다. (힙의 크기가 1이 될때까지 반복)

- Unstable / In-place

최악 시간복잡도	Θ( n log n )
최선 시간복잡도	Θ( n log n )
평균 시간복잡도	Θ( n log n )
공간 복잡도	Θ( 1 )

void heapify(int arr[], int n, int i){
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    // If left child is larger than root
    if(l < n && arr[l] > arr[largest])
        largest = l;
    // If right child is larger than root
    if(r < n && arr[r] > arr[largest])
        largest = r;
    
    // If largest is not root
    if (largest != i){
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n){
    // Build Heap
    for(int i = n / 2 - 1; i>=0; i--)
        heapify(arr, n, i);
    
    for(int i = n - 1; i > 0; i--){
        // move current root to end
        swap(arr[0], arr[i]);
        // heapify on the reduced size
        heapify(arr, i, 0);
    }
}

 

※ Merge Sort Vs Quick Sort :

  Merge Sort 보다 Quick Sort가 선호되는 이유는 Quick Sort가 In-place 이기 때문, Merge Sort의 경우 O(N)의 공간 복잡도를 요구 (이에 필요한 추가 시간 필요).

 

  어떤 입력에 대해서 항상 동일한 반응 시간을 요구하는 시스템에서는 Merge Sort가 적합하다고 할 수 있음, Quick Sort의 경우 특정 데이타의 경우 느린 응답 속도를 보일 수 있다.

 

 하지만 입력 데이타 형식이 array가 아닌 linked list일 경우 Merge Sort가 더 유리, linked list의 경우 index에 따른 접근이 제한적이며 Quick Sort에서는 이런 행우이가 빈번하게 발생한다.