[C/Python] 정렬

[알고리즘] 정렬(Sorting) 정복하기: 기초부터 좌표 압축까지

1. 왜 정렬을 배우는가?

정렬은 단순히 순서대로 나열하는 것을 넘어, 데이터를 효율적으로 탐색(이분 탐색 등)하기 위한 전제 조건입니다. 알고리즘 효율성(O)과 안정성(Stability)을 이해하는 핵심 도구이기도 합니다.

---

2. 핵심 문제 유형별 정리

① 기본 정렬과 시간 복잡도 (2751번, 10989번)

• 포인트: 데이터 개수가 100만 개 이상일 때는 O(N^2)인 삽입/선택/버블 정렬을 쓰면 무조건 '시간 초과'가 납니다.
• 해결: 파이썬의 sort()나 C++의 std::sort(O(N \log N))를 사용해야 합니다.
• 꿀팁: 데이터 범위가 좁다면 **계수 정렬(Counting Sort)**로 O(N)에 끝낼 수도 있습니다.

② 다중 조건 정렬 (1181번, 11650번)

• 문제: "길이 순으로, 같으면 사전 순으로" 같은 조건이 붙을 때.
• Python: key=lambda x: (len(x), x) 처럼 튜플을 반환하는 람다 함수를 쓰면 끝!
• C++: bool compare 함수를 직접 만들어 sort의 세 번째 인자로 전달합니다.

③ 안정 정렬 (Stable Sort) (10814번)

• 개념: 정렬 기준이 같은 데이터끼리 원래의 입력 순서를 유지하는 방식입니다.
• 실무: "나이가 같으면 가입한 순서대로" 같은 조건을 처리할 때 필수입니다.
• 주의: C++의 std::sort는 불안정 정렬이므로, 반드시 **std::stable_sort**를 써야 합니다.

④ 정렬의 응용: 좌표 압축 (18870번)

• 개념: 큰 범위의 좌표값들을 그들의 **상대적인 순서(Rank)**로 변환하는 기법입니다.
• 핵심 로직:
  1. 중복 제거 (set or unique)
  2. 정렬 (sort)
  3. 인덱스 찾기 (Python은 Dictionary, C++은 lower_bound)

---

3. 언어별 성능 최적화 팁 (I/O)

대량의 데이터를 다룰 때는 출력 방식 하나로도 '맞았습니다'가 '시간 초과'로 바뀔 수 있습니다.

• Python: print()를 여러 번 쓰지 말고, "\n".join(result)를 사용해 sys.stdout.write로 한 번에 출력하세요.
• C++: endl 대신 "\n"을 쓰고, ios_base::sync_with_stdio(false); cin.tie(nullptr);를 꼭 넣어주세요.

---

4. 마무리하며

정렬 문제를 풀면서 가장 중요한 것은 **"내 데이터 규모에 맞는 알고리즘을 선택하는 것"**입니다.

• 데이터가 적으면 구현이 쉬운 삽입 정렬!
• 데이터가 많으면 성능이 검증된 내장 sort!
• 중복 제거가 필요하면 **set**이나 unique!