[C++] nlogn sorting 알고리즘 구현

Merge Sort

- 주의할 점은 (l,m-1),(m,r) 로 나누면 (k,k+1) => (k,k-1),(k,k+1) 무한루프 되므로 안 됨. (l, m) (m+1,r) 로 나누자

#include <iostream>
using namespace std;

int N, arr[1000000], arr2[1000000];

void mergeSort(int l, int r) {
    if(l>=r) return;
    int m = (l+r)/2;

    // 각 chunk 정렬
    mergeSort(l, m);
    mergeSort(m+1, r);

    // 두 chunk 합치기
    int ptr1 = l, ptr2 = m+1, ptr = l;
    while(ptr1<=m && ptr2<=r) {
        if(arr[ptr1]<arr[ptr2]) arr2[ptr++] = arr[ptr1++];
        else arr2[ptr++] = arr[ptr2++];
    }
    while(ptr1<=m) arr2[ptr++] = arr[ptr1++];
    while(ptr2<=r) arr2[ptr++] = arr[ptr2++];

    for(int i=l; i<=r; i++) arr[i] = arr2[i];
}

int main() {
    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];

    mergeSort(0, N-1);

    for(int i=0; i<N; i++) cout << arr[i] << "\n";
}

 

Heap Sort

- heapify 함수를 사용해 max heap 생성 및 배열 오름차순 정렬

- index 1부터 사용해야 한다 (이진 트리에서 i <-> 2*i, 2*i+1 이 부모자식 관계 되도록 인덱스 조절)

#include <iostream>
using namespace std;

int N, arr[1000001];

void heapify(int head, int end) {
    int tmp = arr[head];

    int child = head*2;
    while(child<=end) {
        // 자식 node 중 더 큰 것을 고르고
        if(child<end && arr[child]<arr[child+1]) child++;
        // 자신보다 크면 switch, 아니면 반복문 탈출
        if(arr[child]>tmp) {
            arr[child/2] = arr[child];
            child *= 2;
        } else {  
            break;
        }
    }
    arr[child/2] = tmp;
}

int main() {
    cin >> N;
    for(int i=1; i<=N; i++) cin >> arr[i];

    // Max Heap 생성
    for(int i=N/2; i>=1; i--) heapify(i, N);

    // 오름차순 정렬
    for(int i=N; i>=2; i--) {
        int tmp = arr[1];
        arr[1] = arr[i];
        arr[i] = tmp;
        heapify(1,i-1);
    }

    for(int i=1; i<=N; i++) {
        cout << arr[i] << "\n";
    }
}

 

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2