Rustでナチュラルソートを実装する

例

アルファベットと数字が混ざっていたり、ゼロパディングされた数字とされていない数字が混ざっていた場合、通常のソートを使っても文字列で比較しあうので、うまい具合にソートされません。

これを解決するために、例えば以下のような文字列がベクターにある場合に、

1.jpg
10.jpg
00003.jpg
zzz.jpg
02.jpg

以下のようにソートできるように実装します。

1.jpg
02.jpg
00003.jpg
10.jpg
zzz.jpg

コード全体

fn main() {
    let mut v = vec![
        "1.jpg",
        "10.jpg",
        "00003.jpg",
        "zzz.jpg",
        "02.jpg",
    ];
    println!("before: {:?}", v);

    sort_natural(&mut v);

    println!("after: {:?}", v);
}

fn sort_natural(files: &mut [&str]) {
    files.sort_by(|a, b| {
        let a_key = generate_natural_sort_key(a);
        let b_key = generate_natural_sort_key(b);

        let mut cmp_result = std::cmp::Ordering::Equal;
        for (a_part, b_part) in a_key.iter().zip(b_key.iter()) {
            let text_cmp_result = a_part.text.cmp(&b_part.text);
            if text_cmp_result != std::cmp::Ordering::Equal {
                cmp_result = text_cmp_result;
                break;
            }

            let number_cmp_result = a_part.number.cmp(&b_part.number);
            if number_cmp_result != std::cmp::Ordering::Equal {
                cmp_result = number_cmp_result;
                break;
            }
        }

        cmp_result
    })
}

struct NaturalSortKeyPart {
    text: String,
    number: Option<usize>,
}

fn generate_natural_sort_key(s: &str) -> Vec<NaturalSortKeyPart> {
    let mut key = vec![];
    let mut last = 0;
    for (start, end) in extract_number_positions(s) {
        key.push(NaturalSortKeyPart {
            text: s[last..start].to_string(),
            number: s[start..end].parse::<usize>().ok(),
        });
        last = end;
    }

    key.push(NaturalSortKeyPart {
        text: s[last..].to_string(),
        number: None,
    });

    key
}

fn extract_number_positions(s: &str) -> Vec<(usize, usize)> {
    let mut positions = vec![];
    let mut start_index = None;

    for (i, c) in s.char_indices() {
        if c.is_ascii_digit() {
            if start_index.is_none() {
                start_index = Some(i);
            }
        } else if let Some(start) = start_index {
            positions.push((start, i));
            start_index = None;
        }
    }

    if let Some(start) = start_index {
        positions.push((start, s.len()))
    }

    positions
}

実行結果

before: ["1.jpg", "10.jpg", "00003.jpg", "zzz.jpg", "02.jpg"]
after: ["1.jpg", "02.jpg", "00003.jpg", "10.jpg", "zzz.jpg"]

何をしているか

それぞれの関数が何をしているのかを説明していきます。

extract_number_positions

文字列に含まれている数値の開始と終了のインデックスを抽出します。
例えば 1a32.jpg という文字列だったとき、 [(0, 1), (2, 4)] を返却します。
(0, 1) が 1 、 (2, 4) が 32 を表します。

fn extract_number_positions(s: &str) -> Vec<(usize, usize)> {
    let mut positions = vec![];
    let mut start_index = None;

    for (i, c) in s.char_indices() {
        if c.is_ascii_digit() {
            if start_index.is_none() {
                start_index = Some(i);
            }
        } else if let Some(start) = start_index {
            positions.push((start, i));
            start_index = None;
        }
    }

    if let Some(start) = start_index {
        positions.push((start, s.len()))
    }

    positions
}

generate_natural_sort_key

ソートに使用するキーを作成します。
extract_number_positions を使用して文字列の中に含まれる数値のインデックスを取得し、それを使って文字部分、数値部分を抽出してキーを作成します。

struct NaturalSortKeyPart {
    text: String,
    number: Option<usize>,
}

fn generate_natural_sort_key(s: &str) -> Vec<NaturalSortKeyPart> {
    let mut key = vec![];
    let mut last = 0;
    for (start, end) in extract_number_positions(s) {
        key.push(NaturalSortKeyPart {
            text: s[last..start].to_string(),
            number: s[start..end].parse::<usize>().ok(),
        });
        last = end;
    }

    key.push(NaturalSortKeyPart {
        text: s[last..].to_string(),
        number: None,
    });

    key
}

sort_natural

ソートを実際に行う関数です。
generate_natural_sort_key で使用して作成したキーを使います。
キーには文字列に含まれる文字部分と数値部分が含まれており、片方のキーの同じプロパティ同士で比較します。
まずは文字部分同士で比較し、一致していた場合は数値部分同士で比較します。

fn sort_natural(files: &mut [&str]) {
    files.sort_by(|a, b| {
        let a_key = generate_natural_sort_key(a);
        let b_key = generate_natural_sort_key(b);

        let mut cmp_result = std::cmp::Ordering::Equal;
        for (a_part, b_part) in a_key.iter().zip(b_key.iter()) {
            let text_cmp_result = a_part.text.cmp(&b_part.text);
            if text_cmp_result != std::cmp::Ordering::Equal {
                cmp_result = text_cmp_result;
                break;
            }

            let number_cmp_result = a_part.number.cmp(&b_part.number);
            if number_cmp_result != std::cmp::Ordering::Equal {
                cmp_result = number_cmp_result;
                break;
            }
        }

        cmp_result
    })
}