[백준] 2751 : 수 정렬하기2 (C++)

🚩 정렬 알고리즘

📌 합병 정렬 (Merge Sort)

---

📖 문제

BOJ 2751 : 수 정렬하기2

---

🖥 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr, sorted; // 수열, 부분 정렬된 배열

//합병정렬(Conquer & Merge)
void merge(int left, int mid, int right) {
    int p1 = left; //왼쪽 배열 인덱스
    int p2 = mid + 1; //오른쪽 배열 인덱스
    int index = left; //정렬한 배열의 인덱스
    while (p1 <= mid && p2 <= right) {
        if (arr[p1] < arr[p2]) {//왼쪽 배열의 현재 값이 오른쪽 배열의 값보다 작다면
            sorted[index++] = arr[p1++]; //왼쪽 배열 값 저장, 인덱스 증가
        } else {
            sorted[index++] = arr[p2++];
        }
    }
    while (p1 <= mid) { //왼쪽 남아
        sorted[index++] = arr[p1++];
    }
    while (p2 <= right) { //오른쪽 남아
        sorted[index++] = arr[p2++];
    }
    for (int i = left; i <= right; i++) {
        arr[i] = sorted[i];
    }
}

//합병정렬(Divide)
void divide(int left, int right) {
    if (left < right) { //배열 원소 크기가 최소 2
        int mid = (left + right) / 2; //정확히 반으로 나눔
        divide(left, mid); //왼쪽 배열
        divide(mid + 1, right);//오른쪽 배열
        merge(left, mid, right);
    }
}

int main() {
    int n;

    //입력
    cin >> n;
    arr.assign(n, 0);
    sorted.assign(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    //연산
    divide(0, n-1);
    //출력
    for (int i = 0; i < n; i++) {
        cout << arr[i] << '\n';
    }
    return 0;
}

---

💿 결과

5
5
4
3
2
1
1
2
3
4
5

위 코드처럼 합병정렬을 직접 구현해도 되지만, 매번 코드를 작성하는 일이 매우 번거롭다.
따라서, STD 내의 sort함수를 이용해도 된다.

sort 방법

• algorithm내의 함수이므로, 불러와야함
  #include <algorithm>
• 인자로 배열의 처음 시작 위치와, 끝 위치를 보내줌
• default 값은 오름차순 정렬
• 내림차순 정렬은 세 번째 인자에 greater<>() 을 넣어서
• 세 번째 인자에 비교함수(cmp)를 넣어서 원하는 조건대로 정렬 가능
• 비교함수가 false를 리턴할 경우 swap하는 것

---

🖥 더 효율적인 코드

    sort(arr.begin(), arr.end());

begin(), end() 함수를 사용하여 배열의 처음과 끝을 불러올 수 있음

---

©️ 출처

• [BOJ 백준 2751]
  https://www.acmicpc.net/problem/2751

• 알튜비튜