2751) 수 정렬하기 2

문제 요약

크기 n의 숫자 배열이 주어졌을 때, 이 배열을 오름차순으로 정렬하는 문제

풀이

Merge sort사용.
Quick sort: pivot을 기준으로 pivot보다 작은, 큰 집합으로 나누는 알고리즘을 반복하는 정렬 방법
Heap sort: 그래프를 사용하여 그래프의 루트를 가장 큰 숫자로 만드는 makeHeap을 수행하고 가장 마지막 노드와 루트를 교환, 이 알고리즘을 반복적으로 수행해 정렬
Merge를 사용한 이유: Quick은 최악의 경우 O(n^2)의 시간 복잡도. Heap은 지역 참조성이 낮으므로 캐시 예측에 불리

코드

#include <iostream>

void sort(int begin, int end, int *arr);
int main(){
    int num;
    scanf("%d", &num);
    int* arr = new int[num];

    for(int i =0;i<num;i++){
        scanf("%d", &arr[i]);
    }

    sort(0, num,arr);

    for(int i =0;i<num;i++){
        printf("%d\n", arr[i]);
    }


}
void sort(int begin, int end, int *arr){
    if(begin>=(end-1))
        return;

    int num = end - begin;
    int mid = begin + num/2;
    sort(begin, mid, arr);
    sort(mid,end, arr);
    
    int *arr2 = new int[num];
    int i = begin;
    int j = mid;
    int k=0;
  
    while(i<mid&&j<end){
        while(arr[j]> arr[i]&&i<mid&&j<end){
            arr2[k++] = arr[i++];
        }
        while(arr[j]<=arr[i]&&i<mid&&j<end){
            arr2[k++] = arr[j++];
        }
    }
    if(j<end)
        while(j<end){
            arr2[k++] = arr[j++];
        }
    else if(i<mid)
        while(i<mid){
            arr2[k++] = arr[i++];
        }

    i =0;
    for(int k = begin;k<(end);k++){
        arr[k] = arr2[i++];
    }

}