[rust] Rust 언어의 알고리즘

22 Dec 2023

rust

Rust 언어는 안전한 시스템 프로그래밍을 위한 강력한 도구로, 알고리즘 및 데이터 구조를 구현하는 데 매우 적합합니다. 이 포스트에서는 Rust를 사용하여 자주 구현되는 알고리즘들을 살펴보고, 그 예제 코드를 제공하겠습니다.

버블 정렬

Bubble sort는 인접한 두 원소를 비교하고 순서를 바꾸어 정렬하는 간단한 알고리즘입니다. Rust를 사용하여 버블 정렬을 구현한 예제 코드는 다음과 같습니다:

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n-i-1 {
            if arr[j] > arr[j+1] {
                arr.swap(j, j+1);
            }
        }
    }
}

이진 탐색

Binary search는 정렬된 배열에서 특정 원소를 찾는 알고리즘으로, Rust를 사용하여 이진 탐색을 구현한 예제 코드는 다음과 같습니다:

fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len() - 1;

    while low <= high {
        let mid = (low + high) / 2;
        if arr[mid] == target {
            return Some(mid);
        } else if arr[mid] < target {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    None
}

퀵 정렬

Quick sort는 분할 정복 알고리즘으로, 평균적으로 매우 효율적인 정렬 알고리즘입니다. Rust를 사용하여 퀵 정렬을 구현한 예제 코드는 다음과 같습니다:

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    let pivot = arr[0];
    let (mut left, mut right): (Vec<i32>, Vec<i32>) = arr[1..]
        .iter()
        .partition(|&x| x <= pivot);
    quick_sort(&mut left);
    quick_sort(&mut right);
    arr.clone_from_slice(&left);
    arr[left.len()] = pivot;
    arr[(left.len() + 1)..].clone_from_slice(&right);
}

Rust 언어를 사용하여 이 외에도 다양한 알고리즘들을 구현할 수 있습니다. 안전하고 효율적인 시스템 프로그래밍을 위한 Rust의 강력한 특징과 함께 알고리즘을 구현해 보세요!

참고문헌:

목차

버블 정렬

이진 탐색

퀵 정렬