{ }codelper

배우기 › C++

더 나아가기 · 17

정렬

작은 것부터, 큰 것부터, 내가 정한 기준으로 늘어놓기.

정렬은 값을 차례대로 늘어놓는 거예요.
아래 예제는 수를 작은 것부터·큰 것부터 늘어놓고, 단어를 글자 순과 "짧은 것부터" 순으로 늘어놓아요.

#include <algorithm>#include <functional>#include <iostream>#include <sstream>#include <string>#include <vector> template <typename T>void print(const std::vector<T>& v) {    for (size_t i = 0; i < v.size(); i++) std::cout << (i > 0 ? " " : "") << v[i];    std::cout << '\n';} int main() {    std::string line;    std::getline(std::cin, line);    std::istringstream in1(line);    std::vector<int> nums;    for (int x; in1 >> x;) nums.push_back(x);    std::getline(std::cin, line);    std::istringstream in2(line);    std::vector<std::string> words;    for (std::string w; in2 >> w;) words.push_back(w);     std::sort(nums.begin(), nums.end());    print(nums);    std::sort(nums.begin(), nums.end(), std::greater<int>());    print(nums);    std::sort(words.begin(), words.end());    print(words);    std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {        if (a.size() != b.size()) return a.size() < b.size();        return a < b;    });    print(words);}
stdin
10 9 1 25 3
pear fig banana kiwi apple
stdout
1 3 9 10 25
25 10 9 3 1
apple banana fig kiwi pear
fig kiwi pear apple banana

핵심

  • 기본은 수는 크기 순, 문자열은 사전 순(글자 코드 순)이에요.
  • 새 목록을 돌려주는 정렬과 제자리에서 바꾸는 정렬이 있어요.
    Python sorted(nums)는 새 목록, nums.sort()는 제자리예요.
  • 기준을 주는 방법은 둘이에요.
    열쇠 함수는 값마다 비교할 열쇠를 말해요(Python key=lambda w: (len(w), w)는 "길이, 같으면 글자 순").
  • 비교 함수는 두 값을 받아, 앞이 먼저면 음수, 같으면 0, 뒤가 먼저면 양수를 돌려줘요.
  • 안정 정렬은 기준이 같은 값끼리 원래 차례를 지켜요.
    안정이 아닌 정렬에서는 같을 때의 기준(길이가 같으면 글자 순)까지 비교 함수에 적어요.

언어별로 쓰는 법

Pythonsorted(nums)(새 목록), nums.sort()(제자리).
큰 것부터 reverse=True, 기준은 key=lambda w: (len(w), w).
안정적이에요
JavaScriptarr.sort((a, b) => a - b) — 제자리.
비교 함수가 없으면 수도 문자열로 비교해요.
여러 기준은 a.length - b.length || ....
ES2019부터 안정적
TypeScriptJavaScript와 같아요
JavaArrays.sort, Collections.sort.
큰 것부터 Comparator.reverseOrder(), 기준은 Comparator.comparingInt(String::length).thenComparing(...).
객체 배열과 Collections.sort는 안정적.
int[]는 비교 함수를 받지 않아요
C#Array.Sort·List.Sort(제자리, 안정 약속 없음), LINQ OrderBy(...).ThenBy(...)·OrderByDescending(안정적)
C++std::sort(v.begin(), v.end()), 큰 것부터 std::greater<int>().
비교 람다는 "앞이 먼저인가"를 bool로 돌려줘요.
안정이 필요하면 std::stable_sort
Cqsort(a, n, sizeof a[0], cmp) — cmp는 두 포인터를 받아 음수·0·양수를 돌려줘요.
안정 약속 없음
Craykon목록.정렬()은 작은 것부터.
목록.정렬(짧은것먼저)처럼 비교 함수 이름을 넘겨요.
안정적이에요

자주 하는 실수

수를 비교 함수 없이 sort()했어요JavaScript · TypeScript

console.log([10, 9, 1].sort());

→ [ 1, 10, 9 ] — 수를 문자열로 바꿔 비교해요

수는 꼭 (a, b) => a - b를 넘겨요.

nums = nums.sort()라고 썼어요Python

nums = [3, 1, 2]
nums = nums.sort()
print(nums)

→ None — sort는 제자리에서 정렬하고 아무것도 돌려주지 않아요

nums.sort()만 쓰거나, nums = sorted(nums)로 써요.

int[]에 비교 함수를 넘겼어요Java

int[] a = {3, 1, 2};
Arrays.sort(a, Comparator.reverseOrder());

→ 컴파일 오류 — int[]용 sort는 비교 함수를 받지 않아요

예제처럼 Integer[]로 바꾸거나, 작은 것부터 정렬한 뒤 거꾸로 읽어요.

언어마다 다른 점
C qsort 비교 함수를 return a - b;로 쓰면 큰 음수와 큰 양수를 뺄 때 int가 넘쳐(예: -2000000000 - 2000000000) 부호가 뒤집히고 순서가 틀려요.
(a > b) - (a < b)처럼 비교로 쓰세요.

연습 문제

  1. 수 정렬하기8P0036
  2. 단어 빈도 순위8P0034
  3. 간판 글자 조각 정리8P0253
  4. 수 크기 순서와 사전 순서8P0320
  5. 생일이 빨리 돌아오는 친구부터8P0376
  6. 성적 순위표8P0067
  7. 회의실 하나에 회의 많이 넣기8P0090
  8. 합집합 교집합 차집합8P0099