백준 2751 - 수 정렬하기2(합병정렬(Merge sort), 힙정렬(heap sort))

0. 주어진 문제

수 정렬하기 2 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	37424	11398	7353	34.238%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

1. 풀이

1) heap sort를 활용하기로 결정하였다.

2) 문제를 풀며 정확히 구현한 것 같았는데 계속 잘못된 결과가 출력되는 경우가 반복되었었다.

원인을 찾아보니 sord_heap(std::vector<int> heap)으로 표현을 해놓았기에 정렬을 한 결과가 main()함수 부분의 heap으로 연결이 되질 않았었다.

 따라서 sord_heap(std::vector<int>& heap)으로 표현을 바꾸니 원하는 결과를 출력해 낼 수 있었다.

+) 추가

사실 <algorithm>에 속해있는 sort라는 함수를 사용하면 퀵 정렬을 할 수 있다.

평균 수행시간은 n log n이므로 내가 한 구현과 큰 차이는 없었을 것이다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include <iostream> #include <vector>        //이건 말 그대로 vector를 사용하기 위함 #include <algorithm>    //swap을 사용하기 위해서     void push_heap(std::vector<int>& heap, int newValue) {     //힙의 맨 끝에 newValue를 삽입한다.     heap.push_back(newValue);     //현재 newValue의 위치     int idx = heap.size() - 1;     //루트에 도달하거나 newValue 이상의 원소를 가진 조상을 만날 때까지     while (idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {         std::swap(heap[idx], heap[(idx - 1) / 2]);         idx = (idx - 1) / 2;     } }     //이왕 구현한거 끝까지 //정수 원소를 갖는 최대 힙에서 최대 원소 삭제하기 void pop_heap(std::vector<int>& heap) {     //heap의 맨 끝에서 값을 가져와 루트에 덮어씌운다.     heap[0] = heap.back();     heap.pop_back();     int here = 0;     while (true) {         int left = here * 2 + 1, right = here * 2 + 2;         //리프에 도달한 경우         if (left >= heap.size()) break;         //heap[here]가 내려갈 위치를 찾는다.         int next = here;         if (heap[next] < heap[left]) next = left;         if (right < heap.size() && heap[next] < heap[right]) next = right;         if (next == here) break;         std::swap(heap[here], heap[next]);         here = next;     } }   //문제부분 heap sort를 구현하자. //위의 부분을 조금 활용해보았다. void sort_heap(std::vector<int>& heap) {     for (int count = 1;count < heap.size();count++) {         std::swap(heap[heap.size() - count] ,heap[0]);         int here = 0;         while (true) {             int left = here * 2 + 1, right = here * 2 + 2;             //리프에 도달한 경우             if (left >= heap.size()-count) break;             //heap[here]가 내려갈 위치를 찾는다.             int next = here;             if (heap[next] < heap[left]) next = left;             if (right < heap.size()-count && heap[next] < heap[right]) next = right;             if (next == here) break;             std::swap(heap[here], heap[next]);             here = next;         }     } }       int main(void) {     int n;     std::cin >> n;     std::vector<int> heap;     for (int t = 0;t < n;t++) {         int a;         std::cin >> a;         push_heap(heap, a);     }     sort_heap(heap);     for (auto a: heap)         std::cout << a << "\n"; } Colored by Color Scripter

cs

+ 추가) quick sort활용

#include <iostream>
#include <algorithm>
 
int arr[1000001];
int main()
{
    int n, i;
    std::cin >> n;
    for (i = 0;i<n;i++) {
        std::cin >> arr[i];
    }
    std::sort(arr, arr+n);
    for (i = 0;i < n;i++) {
        std::cout << arr[i] << "\n";
    }
}
 

3. 문제 출처

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

4. 참고

힙정렬 - https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

합병 정렬 - https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.728~729.