Quick Sort 와 Merge Sort

❓Merge Sort란?

int sorted_arr[10];

void Sort(int *arr, int start, int mid, int end){
    int i = start;
    int j = mid+1;
    int k = start;

    while(i<=mid && j<=end){
        if(arr[i] <= arr[j]){
            sorted_arr[k]=arr[i];
            i++;
        }
        else{
            sorted_arr[k]=arr[j];
            j++;
        }
        k++;
    }

    if(i>mid){
        for(int t=j;t<=end;t++){
            sorted_arr[k]=arr[t];
            k++;
        }
    }
    else{
        for(int t=i;t<=mid;t++){
            sorted_arr[k]=arr[t];
            k++;
        }
    }

    for(int t=start;t<=end;t++){
        arr[t] = sorted_arr[t];
    }
}

void Merge_Sort(int* arr, int start, int end){

    if(start < end){
        int mid = (start + end) / 2;

        Merge_Sort(arr, start, mid);
        Merge_Sort(arr, mid+1, end);
        Sort(arr, start, mid, end);
    }
}

int main(){
    int arr[10] = {1,7,3,5,4,50,24,8,9,6};

    Merge_Sort(arr, 0,9);

    for(int i=0;i<10;i++){
        cout << arr[i] << " ";
    }
}

분할 정복(Divide and Conquer)을 이용한 정렬 방법
Stable한 정렬

요소들을 절반으로 쪼개고 다시 합병 시키며 정렬하는 방식

❓Quick Sort란?

using namespace std;

// Quick Sort 재귀 버전

void Quick_Sort(int* arr, int low, int high){
    if(low >= high) return;

    // 가장 마지막 숫자가 Pivot
    int i =low, j=low;
    int pivot = arr[high];

    for(; j<high ; j++){
        if(arr[j] < pivot){
            swap(arr[i++], arr[j]);
        }
            
    }
    swap(arr[i], arr[high]);

    Quick_Sort(arr, low, i-1);
    Quick_Sort(arr, i+1, high);
}

int main(){
    int arr[10] = {1,7,3,5,4,50,24,8,9,6};

    Quick_Sort(arr, 0, 9);

    for(int i=0;i<10;i++){
        cout << arr[i] << " ";
    }
}

분할 정복(Divide and Conquer)을 이용한 정렬 방법
Unstable한 정렬

Pivot을 선택하고, Pivot 보다 작은 수와 Pivot 보다 큰 수로 분할하여 정렬

❓Merge Sort와 Quick Sort의 차이점은?

출처 : https://www.bigocheatsheet.com/

1. Merge Sort의 Time Complexity는 Worst, Average, Best 모두 nlog(n) 시간을 가진다.
   Quick Sort의 Time Complexity는 Worst, Average, Best가 n^2, nlog(n), nlog(n)을 가진다.

2. Merge Sort의 Space Complexity는 n이고 Quick Sort의 Space Complexity는 log(n)이다.

❓Merge Sort와 Quick Sort는 언제 사용해야 할까?

메모리가 한정된 상황에서는 Quick Sort를 사용
어떤 상황에서도 시간을 준수 해야한다면 Merge Sort 사용