02_sorting.md

정렬 (Sorting)

📌 개념

배열을 특정 순서(오름차순/내림차순)로 재배열하는 알고리즘

🎯 언제 사용하나?

문제에서 이렇게 나옵니다

• "오름차순/내림차순으로 정렬"
• "K번째로 큰/작은 원소" → 정렬 후 인덱싱
• "이분 탐색 전 필수"
• "그리디 알고리즘" → 정렬 후 앞/뒤부터 처리
• "좌표/시간 기준 정렬" → 커스텀 비교 함수

💡 Tip

• 대부분 문제에서 STL/내장 정렬 사용! (직접 구현 ❌)
• 안정 정렬 필요 시: stable_sort (C++) 또는 기본 sort (Python)

⏱️ 시간복잡도

알고리즘	평균	최악	안정성
버블 정렬	O(N²)	O(N²)	✅
선택 정렬	O(N²)	O(N²)	❌
삽입 정렬	O(N²)	O(N²)	✅
병합 정렬	O(NlogN)	O(NlogN)	✅
퀵 정렬	O(NlogN)	O(N²)	❌
힙 정렬	O(NlogN)	O(NlogN)	❌
계수 정렬	O(N+K)	O(N+K)	✅

💡 실전에서는 STL/내장 정렬 사용! (C++: sort(), Python: sorted())

💻 C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {5, 2, 8, 1, 9};
    
    // 오름차순
    sort(arr.begin(), arr.end());
    
    // 내림차순
    sort(arr.begin(), arr.end(), greater<int>());
    
    // 커스텀 정렬 (pair: 첫번째 기준 오름차순, 같으면 두번째 기준 내림차순)
    vector<pair<int,int>> v = {{1,3}, {1,2}, {2,1}};
    sort(v.begin(), v.end(), [](auto& a, auto& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    });
    
    return 0;
}

🐍 Python 코드

arr = [5, 2, 8, 1, 9]

# 오름차순
arr.sort()
# 또는
sorted_arr = sorted(arr)

# 내림차순
arr.sort(reverse=True)

# 커스텀 정렬 (튜플: 첫번째 기준 오름차순, 같으면 두번째 기준 내림차순)
v = [(1,3), (1,2), (2,1)]
v.sort(key=lambda x: (x[0], -x[1]))

🎯 핵심 응용

1. 좌표 정렬: (x, y) 정렬 시 x 우선, y 차선
2. 안정 정렬: 같은 키값의 상대적 순서 유지 필요 시
3. K번째 원소: 정렬 후 인덱싱 or nth_element (O(N))

📖 외부 자료

• Sorting Algorithms - VisuAlgo
• C++ sort() 함수
• Python sorted() 함수

📚 연습 문제

• BOJ 2751 수 정렬하기 2
• BOJ 11650 좌표 정렬하기 ⭐
• BOJ 10814 나이순 정렬 ⭐ 안정 정렬
• BOJ 11004 K번째 수