1. 정렬

정렬

빠른 설명

정렬은 데이터를 특정 기준에 따라 오름차순 또는 내림차순으로 재배열하는 것이다. 문제 풀이에서는 직접 정렬 알고리즘을 구현하기보다, 대부분 C++의 sort, Python의 sort/sorted를 사용한다.

언제 쓰는가

• 가장 작은 값, 가장 큰 값, 중앙값, 순위가 필요할 때
• 같은 값끼리 묶거나 중복을 제거할 때
• 이진 검색, 투 포인터, 그리디의 전처리로 사용할 때

시간복잡도

• 일반 정렬: 보통 $O(N\log N)$
• 이미 정렬된 배열을 한 번 훑기: $O(N)$

참고자료

• Wikipedia - Sorting algorithm
• cppreference - std::sort
• Python Sorting HOWTO
• GeeksforGeeks - Sorting Algorithms

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<int> a = {5, 1, 4, 2, 3};
 
    sort(a.begin(), a.end());               // 오름차순
    sort(a.begin(), a.end(), greater<int>()); // 내림차순
 
    for (int x : a) cout << x << ' ';
}

Python 코드

a = [5, 1, 4, 2, 3]
 
a.sort()                  # 오름차순, 원본 변경
b = sorted(a, reverse=True)  # 내림차순, 새 리스트
 
print(a)
print(b)