9 エッヂの名無し 2024/06/23(日) 12:03:35.979 ID:KShm0KmsW
再帰2回使う例としてマージソート実装してたら落ちてた
fn merge_sort(abeshinzou: Vec<u32>) -> Vec<u32> {
if abeshinzou.len() <= 1 {
return abeshinzou;
}
// abeshinzouを前半と後半に分割
let (abe, shinzou) = abeshinzou.split_at(abeshinzou.len() / 2);
let abe = abe.to_vec();
let shinzou = shinzou.to_vec();
// abe, shinzouに対して再帰
let abe = merge_sort(abe);
let shinzou = merge_sort(shinzou);
// ここでabeとshinzouをマージする
let mut abeshinzou = Vec::new();
let mut idx_a = 0;
let mut idx_b = 0;
while idx_a < abe.len() || idx_b < shinzou.len() {
let mut is_abe_push = false;
if idx_b == shinzou.len() || (idx_a < abe.len() && abe[idx_a] < shinzou[idx_b]) {
is_abe_push = true;
}
if is_abe_push {
abeshinzou.push(abe[idx_a]);
idx_a += 1;
} else {
abeshinzou.push(shinzou[idx_b]);
idx_b += 1;
}
}
return abeshinzou;
}
fn main() {
let abeshinzou = vec![2, 0, 2, 2, 0, 7, 0, 8];
// let abeshinzou = vec![1, 1, 4, 5, 1, 4];
println!("{:?}", abeshinzou);
let abeshinzou = merge_sort(abeshinzou);
println!("{:?}", abeshinzou);
}