Rust 정렬과 검색

정렬과 검색은 거의 모든 프로그램에서 하게 되는 작업이에요. 점수로 플레이어 순위 매기기, 이름순으로 파일 나열하기, 가장 싼 상품 찾기 같은 일들이죠. Rust는 벡터와 슬라이스에 두 작업을 위한 메서드를 기본으로 제공해서, 알고리즘을 직접 짤 일은 거의 없어요.

이 메서드들은 대부분 두 요소를 어떻게 비교할지 알려 주는 클로저를 받아요. 이 아이디어 하나에 익숙해지면, 이 페이지의 나머지는 그 변형일 뿐이에요.

sort와 sort_unstable

.sort()는 요소를 오름차순(작은 것부터)으로 정렬해요. 벡터를 그 자리에서 바꾸기 때문에 벡터는 mut여야 해요. 숫자는 값 크기로, 문자열은 알파벳순으로 정렬돼요.

fn main() {
    let mut scores = vec![42, 7, 99, 7, 15];
    scores.sort();
    println!("{:?}", scores);

    let mut names = vec!["Zoe", "adam", "Bob", "Ana"];
    names.sort_unstable();
    println!("{:?}", names);
}

실행 결과:

[7, 7, 15, 42, 99]
["Ana", "Bob", "Zoe", "adam"]

▶ 직접 실행해 보기

눈여겨볼 점이 두 가지 있어요.

"adam"이 맨 마지막에 와요. 문자열은 문자 코드로 비교되는데, 대문자는 모두 소문자보다 앞에 오거든요. “사전” 순서를 원한다면 name.to_lowercase()로 정렬하세요(아래에서 보여 줄게요). 이 예제의 이름을 영어로 둔 것도 이 대소문자 차이를 보여 주기 위해서예요.
sort_unstable은 보통 조금 더 빠르고 추가 메모리를 쓰지 않아요. “불안정(unstable)“하다는 건 버그가 있다는 뜻이 아니에요. 같다고 비교되는 요소끼리 자리가 바뀔 수 있다는 뜻이에요. 평범한 숫자나 문자열에서는 그 차이를 알 수 없으니, 기본으로 써도 괜찮아요.

역순으로 정렬하기

큰 것부터 작은 것 순으로 정렬하는 흔한 방법이 세 가지 있어요. 여기서는 세 가지 모두 같은 결과를 내요.

use std::cmp::Reverse;

fn main() {
    let mut a = vec![3, 8, 1, 5];
    a.sort();
    a.reverse();
    println!("{:?}", a);

    let mut b = vec![3, 8, 1, 5];
    b.sort_by(|x, y| y.cmp(x)); // x 대신 y를 먼저 = 내림차순
    println!("{:?}", b);

    let mut c = vec![3, 8, 1, 5];
    c.sort_by_key(|&n| Reverse(n));
    println!("{:?}", c);
}

실행 결과:

[8, 5, 3, 1]
[8, 5, 3, 1]
[8, 5, 3, 1]

▶ 직접 실행해 보기

x.cmp(y)는 Ordering을 돌려줘요. Less, Equal, Greater 중 하나예요. sort_by는 이 값으로 어느 요소를 앞에 둘지 정해요. y.cmp(x)라고 쓰면 모든 판단이 뒤집히니까, 전체 순서도 뒤집혀요. Reverse는 std::cmp에 있는 작은 래퍼(wrapper)로, 키에 대해 같은 뒤집기를 해 줘요.

실수(float) 정렬하기

f64 벡터에 .sort()를 써 보면 Rust가 거부해요.

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0];
    prices.sort();
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
 --> src/main.rs:3:12
  |
3 |     prices.sort();
  |            ^^^^ the trait `Ord` is not implemented for `{float}`

“실수 타입에 Ord 트레이트가 구현되어 있지 않다”는 에러예요. 왜 그럴까요? .sort()에는 전순서(total order, Ord 트레이트)가 필요해요. 어떤 두 값이든 한쪽이 작거나, 같거나, 커야 한다는 뜻이에요. 그런데 실수에는 NaN(“숫자가 아님”)이라는 특별한 값이 있어요. NaN은 어떤 값보다도 작지도, 같지도, 크지도 않아요. 자기 자신과도요. 그래서 실수에는 PartialOrd만 있고, .partial_cmp()는 Option<Ordering>을 돌려주는데 NaN이면 None이 돼요.

좋은 해결 방법이 두 가지 있어요.

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0, 4.75];

    // NaN이 없다고 확신할 수 있을 때:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // NaN이 있어도 동작해요(NaN은 맨 뒤로 가요):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

실행 결과:

[0.99, 2.5, 4.75, 10.0]
[-1.0, 0.5, 3.2, NaN]

▶ 직접 실행해 보기

partial_cmp(...).unwrap()은 NaN을 만나면 패닉이 일어나요. total_cmp는 NaN을 포함한 모든 실수에 정해진 자리를 매기기 때문에 절대 패닉이 일어나지 않아요. 특별한 이유가 없다면 total_cmp를 쓰세요.

sort_by_key와 구조체 정렬

sort_by_key는 무엇을 기준으로 정렬할지 고르는 클로저를 받아요. 필드를 골라서 정렬하는 구조체에 딱 맞아요.

#[derive(Debug)]
struct Product {
    name: String,
    price_cents: u32,
}

fn main() {
    let mut items = vec![
        Product { name: String::from("pen"), price_cents: 150 },
        Product { name: String::from("Notebook"), price_cents: 499 },
        Product { name: String::from("eraser"), price_cents: 75 },
    ];

    items.sort_by_key(|p| p.price_cents);
    for p in &items {
        println!("{} - {}", p.price_cents, p.name);
    }

    items.sort_by_key(|p| p.name.to_lowercase());
    let names: Vec<&str> = items.iter().map(|p| p.name.as_str()).collect();
    println!("{:?}", names);
}

실행 결과:

75 - eraser
150 - pen
499 - Notebook
["eraser", "Notebook", "pen"]

▶ 직접 실행해 보기

키 클로저는 소유한 값을 돌려줘야 해요. p.price_cents는 복사되는 u32라서 괜찮아요. String 필드라면 새 String이 필요해요. 그래서 두 번째 정렬에서는 새 문자열을 만들어 주는 to_lowercase()를 썼어요. (아래 “자주 하는 실수”를 참고하세요.)

여러 필드로 정렬하기

자주 나오는 과제예요. 학생들을 점수 높은 순으로 정렬하되, 점수가 같으면 이름 알파벳순으로 정렬해 보죠. sort_by와 .then_with()를 쓰면 돼요. .then_with()는 첫 번째 비교가 동점일 때만 두 번째 비교를 봐요.

struct Student {
    name: String,
    grade: u32,
}

fn main() {
    let mut class = vec![
        Student { name: String::from("Liam"), grade: 88 },
        Student { name: String::from("Ava"), grade: 95 },
        Student { name: String::from("Noah"), grade: 88 },
        Student { name: String::from("Emma"), grade: 88 },
        Student { name: String::from("Mia"), grade: 72 },
    ];

    class.sort_by(|a, b| {
        b.grade.cmp(&a.grade)               // 점수: 높은 순
            .then_with(|| a.name.cmp(&b.name)) // 그다음 이름: 알파벳순
    });

    for s in &class {
        println!("{:>3}  {}", s.grade, s.name);
    }
}

실행 결과:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ 직접 실행해 보기

더 짧게 쓰는 방법으로, 키로 튜플을 돌려줄 수도 있어요. 튜플은 첫 번째 요소를 비교하고, 같으면 두 번째를 비교하는 식으로 동작해요.

class.sort_by_key(|s| (Reverse(s.grade), s.name.clone()));

이렇게 해도 순서는 똑같아요. 깔끔하긴 하지만 이름을 전부 복제(clone)하기 때문에, 목록이 크다면 sort_by와 then_with를 쓰는 습관이 더 좋아요.

dedup으로 중복 제거하기

.dedup()은 바로 앞의 요소와 같은 요소를 제거해요. 그래서 목록을 먼저 정렬해야만 모든 중복이 사라져요.

fn main() {
    let mut tags = vec!["rust", "web", "rust", "cli", "web", "web"];

    let mut not_sorted = tags.clone();
    not_sorted.dedup();
    println!("dedup만: {:?}", not_sorted);

    tags.sort();
    tags.dedup();
    println!("sort + dedup: {:?}", tags);
}

실행 결과:

dedup만: ["rust", "web", "rust", "cli", "web"]
sort + dedup: ["cli", "rust", "web"]

▶ 직접 실행해 보기

첫 번째 시도에서는 나란히 붙어 있던 "web" 두 개만 합쳐졌어요. 먼저 정렬하고, 그다음에 dedup하세요. 원래 순서를 유지해야 한다면 HashSet 페이지의 HashSet 요령을 쓰세요.

검색: contains, position, max, min, binary_search

가장 자주 쓰게 될 검색 도구들이에요.

contains(&x): 들어 있나요? bool을 돌려줘요.
iter().position(...): 처음으로 조건에 맞는 위치는 어디인가요? Option<usize>를 돌려줘요.
iter().max() / iter().min(): 가장 큰 값과 가장 작은 값을 Option으로 돌려줘요(빈 목록이면 None).
iter().max_by_key(...) / min_by_key(...): 어떤 필드를 기준으로 가장 큰 것이나 가장 작은 것을 찾아요.
binary_search(&x): 아주 빠른 검색이지만, 정렬된 목록에서만 쓸 수 있어요. 찾으면 Ok(index)를, 못 찾으면 그 값이 들어갈 자리를 알려 주는 Err(index)를 돌려줘요.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("31이 있나요? {}", temps.contains(&31));
    println!("처음으로 20보다 큰 위치: {:?}", temps.iter().position(|&t| t > 20));
    println!("최댓값: {:?}, 최솟값: {:?}", temps.iter().max(), temps.iter().min());

    let players = vec![("ana", 340), ("ben", 515), ("chen", 220)];
    let best = players.iter().max_by_key(|(_, score)| *score).unwrap();
    println!("1등 플레이어: {}", best.0);

    let mut sorted = vec![10, 20, 30, 40];
    println!("{:?}", sorted.binary_search(&30));
    let missing = sorted.binary_search(&25);
    println!("{:?}", missing);
    if let Err(pos) = missing {
        sorted.insert(pos, 25); // 목록이 정렬된 상태로 유지돼요
    }
    println!("{:?}", sorted);
}

실행 결과:

31이 있나요? true
처음으로 20보다 큰 위치: Some(1)
최댓값: Some(31), 최솟값: Some(12)
1등 플레이어: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ 직접 실행해 보기

binary_search(이진 탐색)는 가운데 요소를 확인하고, 값이 있을 수 없는 절반을 버리고, 이를 반복해요. 요소가 백만 개인 목록이라면 최대 백만 번이 아니라 약 20번만 확인하면 돼요. Err(pos) 결과도 쓸모가 있어요. pos에 값을 넣으면 목록이 정렬된 상태로 유지되거든요.

자주 하는 실수

sort_by_key에서 대여한 String 필드를 그대로 돌려주기. 자연스러워 보이지만 컴파일되지 않아요.

students.sort_by_key(|s| s.name);

error[E0507]: cannot move out of `s.name` which is behind a shared reference
  --> src/main.rs:12:30
   |
12 |     students.sort_by_key(|s| s.name);
   |                              ^^^^^^ move occurs because `s.name` has type `String`, which does not implement the `Copy` trait

“공유 참조자 뒤에 있는 s.name을 밖으로 이동할 수 없다”는 에러예요. 클로저는 각 학생을 대여하기만 하니까, String을 넘겨줄 수 없어요. 복제하거나(|s| s.name.clone()), sort_by(|a, b| a.name.cmp(&b.name))로 복사 자체를 피하세요.

정렬되지 않은 목록에 binary_search 쓰기. 프로그램이 멈추지는 않지만, 결과에 의미가 없어요. 값이 바로 거기 있는데도 없다고 할 수 있어요. 항상 먼저 정렬하거나, 대신 contains / position을 쓰세요.

연습 문제

1. 순위표

플레이어가 (이름, 점수) 튜플로 있어요: ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). 점수가 높은 순으로 정렬하고, 동점이면 이름 알파벳순으로 정렬하세요. 상위 세 명만 출력해 보세요. 힌트: sort_by와 .then_with()를 쓰고, 상위 세 명은 슬라이스 &players[..3]로 가져오세요.

정답 보기

fn main() {
    let mut players = vec![("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60)];

    players.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

    for (name, score) in &players[..3] {
        println!("{score} {name}");
    }
}

실행 결과:

95 ana
88 dev
70 ben

▶ 직접 실행해 보기

튜플에서 .0은 이름이고 .1은 점수예요. ben과 chen이 둘 다 70점이라 이름으로 순서가 정해지고, ben이 상위 세 명에 들어가요.

2. 가격의 중앙값

가격 3.5, 1.25, 9.0, 4.75, 2.0의 중앙값(가운데 값)을 구해 보세요. 정렬된 목록과 중앙값을 출력하세요. 힌트: total_cmp로 정렬하면, 길이가 홀수인 목록의 가운데 요소는 인덱스 len() / 2에 있어요.

정답 보기

fn main() {
    let mut prices: Vec<f64> = vec![3.5, 1.25, 9.0, 4.75, 2.0];

    prices.sort_by(|a, b| a.total_cmp(b));
    let median = prices[prices.len() / 2];

    println!("정렬 결과: {:?}", prices);
    println!("중앙값: {median}");
}

실행 결과:

정렬 결과: [1.25, 2.0, 3.5, 4.75, 9.0]
중앙값: 3.5

▶ 직접 실행해 보기

Vec<f64> 타입 표기가 중요해요. 이게 없으면 Rust는 total_cmp에 도달했을 때 숫자들이 어떤 실수 타입인지 아직 몰라서, “no method named total_cmp”(total_cmp라는 메서드가 없다)라는 에러를 내며 컴파일을 거부해요.

정리

sort()와 sort_unstable()은 그 자리에서 작은 것부터 정렬해요. 큰 것부터 정렬하려면 reverse(), y.cmp(x), 또는 Reverse를 쓰세요.
실수는 NaN 때문에 sort()를 쓸 수 없어요. sort_by(|a, b| a.total_cmp(b))를 쓰세요.
sort_by_key는 고른 필드로 정렬하고, sort_by와 .then_with()는 여러 필드로 정렬해요.
dedup()은 서로 붙어 있는 같은 요소만 제거하니까, 먼저 정렬하세요.
contains, position, max/min, max_by_key는 어떤 목록에서든 검색할 수 있어요. binary_search는 훨씬 빠르지만 정렬된 목록이 필요해요.

이해도 점검

1. vec![1.5, 0.5].sort()가 컴파일되지 않는 이유는 무엇인가요?

2. vec![1, 1, 2, 1].dedup() 후에 벡터에는 무엇이 남나요?

3. vec![10, 20, 30].binary_search(&25)는 무엇을 돌려주나요?

4. a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name))에서 이름은 언제 비교되나요?

점수: 0 / 4

더 알아보기

슬라이스 메서드: sort, sort_by, binary_search 등 — 표준 라이브러리 문서 (영어): 모든 정렬·검색 메서드를 속도와 안정성에 대한 설명과 함께 볼 수 있어요.
std::cmp::Ordering — 표준 라이브러리 문서 (영어): Less, Equal, Greater와 then, then_with, reverse를 설명해요.
std::cmp::Reverse — 표준 라이브러리 문서 (영어): 키를 큰 것부터 정렬할 때 쓰는 래퍼예요.
f64::total_cmp — 표준 라이브러리 문서 (영어): 실수를 정렬할 때 NaN, 음수 0, 무한대가 정확히 어디에 놓이는지 알려 줘요.
Sort a Vector — Rust Cookbook (영어): 정수, 실수, 구조체를 정렬하는 짧은 레시피들이에요.