RUST QuickSortの見直し

2023年1月6日

だめだったか。おれには関係ないやとマイペースな柴犬です。

sort 部分の見直し

次のようにソート部分を見直しましたが、残念ながら効果は感じられませんでした。

クイックソートから外れますが、構造体を要素にしたベクトルを作ってみて、O’reilly プログラミングRust第2版にある16.2.8 ソートと検索にある次のコードを使ってどのくらいでできるのか確かめたいと思います。

students.sort_by(|a, b| {
    let a_key = (&a.last_name, &a.first_name);
    let b_key = (&b.last_name, &b.first_name);
    a_key.cmp(&b_key)
});

引き続き考えてみます。

copy

fn partition<T: PartialOrd + Clone>(
    elements: &mut Vec<Vec<T>>,
    left: usize,
    right: usize,
) -> usize {
    let pivot1 = elements[left][0].clone();
    let pivot2 = elements[left][1].clone();
    let mut i = left + 1;
    let mut j = right;
    loop {
        // i, j の取り得る範囲は left + 1 <= i, j <= right
        // 条件を満たす限り i を進めます。
        while i <= right
            && (elements[i][0].clone() < pivot1
                || (elements[i][0].clone() == pivot1 && elements[i][1].clone() < pivot2))
        {
            i += 1;
        }
        // 条件を満たす限り j を進めます。
        // 同値に対応するため　.clone() > pivot2 を .clone() >= pivot2 としました。
        while j >= left + 1
            && (elements[j][0].clone() > pivot1
                || (elements[j][0].clone() == pivot1 && elements[j][1].clone() >= pivot2))
        {
            j -= 1;
        }
        // 交差になれば入れ替えます。
        if i >= j {
            break;
        }
        swap(elements, i, j);
    }
    // ピボットを正しい位置にセットします。
    swap(elements, left, j);
    return j as usize;
}

fn swap<T: PartialOrd + Clone>(elements: &mut Vec<Vec<T>>, i1: usize, i2: usize) {
    if i1 < i2 {
        let mut temp = elements[i2][0].clone();
        elements[i2][0] = elements[i1][0].clone();
        elements[i1][0] = temp;
        temp = elements[i2][1].clone();
        elements[i2][1] = elements[i1][1].clone();
        elements[i1][1] = temp;
    }
}

fn quicksort<T: PartialOrd + Clone>(elements: &mut Vec<Vec<T>>, left: usize, right: usize) {
    if left < right {
        let pivot = partition(elements, left, right);
        // オーバーフローのエラーがでるが
        // 実際は pivot == 0 になると underflow エラー
        if pivot < 1 {
            quicksort(elements, left, left);
        } else {
            quicksort(elements, left, pivot - 1);
        }
        quicksort(elements, pivot + 1, right);
    }
}