[基礎]Sorting Algorithm 確認: O(n log n)のアルゴリズム集

Merge Sort

再帰的に配列を半分にして統合する。安定ソート。

pub fn merge_sort(nums: &[i32]) -> Vec<i32> {
    if nums.len() <= 1 { // 要素数が1以下になったら終了
        return nums.to_vec(); 
    }
    let mid = nums.len() / 2;
    let left = &nums[0..mid];
    let right = &nums[mid..];
    let sorted_left = merge_sort(left);
    let sorted_right = merge_sort(right);
    merge(&sorted_left, &sorted_right)
}

fn merge(left: &[i32], right: &[i32]) -> Vec<i32> {
    let left_len = left.len();
    let right_len = right.len();
    let mut merged = Vec::with_capacity(left_len + right_len);

    let mut l = 0;
    let mut r = 0;

    for _ in 0..(left_len + right_len) {
        match (left.get(l), right.get(r)) {
            (None, None) => break,
            (None, Some(r_n)) => {
                merged.push(*r_n);
                r += 1;
            }
            (Some(l_n), None) => {
                merged.push(*l_n);
                l += 1;
            }
            (Some(l_n), Some(r_n)) => {
                if l_n > r_n { // 安定ソートにする
                    merged.push(*r_n);
                    r += 1;
                } else {
                    merged.push(*l_n);
                    l += 1;
                }
            }
        }
    }

    merged
}

配列を半分に分割し、それぞれソートしたうえでの２つの配列をマージする操作を再帰的に繰り返す。
再起が止まるのは、配列の要素数が1以下になるとき。
実際にソートが実行されるのはmergeの中。２つのソート済みの配列を順に入れ込んでいく。
このとき、安定ソートにするために同じものは左の要素を優先することにする。

merge sortは配列をシーケンシャルに走査するので、CPUプリフェッチの性能はいいが、新しい配列を用意してマージしていくのでキャッシュヒット率は低い

Quick Sort

pub fn quick_sort(nums: &mut [i32]) {
    if nums.len() <= 1 {
        return;
    }

    let pivot = partition(nums);

    // pivotを除いてsort
    // pivotを基準にするとすでにソートされているため
    quick_sort(&mut nums[0..pivot]);
    quick_sort(&mut nums[pivot + 1..]);
}

fn partition(nums: &mut [i32]) -> usize {
    let pivot = nums[nums.len() / 2];
    nums.swap(nums.len() / 2, nums.len() - 1); // pivotを末尾に移動

    let mut i_less_than_pivot = 0;
    for j in 0..nums.len() - 1 {
        if nums[j] <= pivot {
            nums.swap(i_less_than_pivot, j);
            i_less_than_pivot += 1;
        }
    }
    nums.swap(i_less_than_pivot, nums.len() - 1); // pivotを正しい位置に復帰
    i_less_than_pivot
}

配列から適当なpartitionを選択し、それを基準に大小で配列を２つにわける。これを再帰的に実行する。partitionの選択効率がquick sortの効率に依存し、partitionの選択によって、配列が偏った分割をされると最悪実行時間がO(n^2)となってしまう。

pivotの選択をどこにしても、一旦末尾に移動しておくほうがいい。
pivotを基準とした並び替えのなかでpivotの位置を追跡する必要がなくなる。部分配列のquick sortは再帰処理で同じメモリ領域を再利用するのでキャッシュヒット率が上がりやすい。

Heap Sort

Priority Queueの中身。二分木で、節点の値がその親の値以下（以上）であるという条件を満たす。これをヒープ条件と呼ぶ。
これを配列で表現している。
先頭の要素が、根で、index iの左の子は2i, 右の子は2i + 1となる。

与えられた配列に対し、ヒープを構築 -> 先頭の要素を末尾に移動し、heap_sizeを一つ減らしてheapifyを実行

pub fn heap_sort(nums: &mut [i32]) {
    for i in (0..(nums.len() / 2)).rev() {
        // ここまでの要素をheapifyすれば十分
        min_heapify(nums, nums.len(), i)
    }
    let mut heap_size = nums.len() - 1;
    for i in (0..nums.len()).rev() {
        nums.swap(0, i);
        heap_size -= 1;
        min_heapify(nums, heap_size, 0);
    }
}

fn min_heapify(nums: &mut [i32], heap_size: usize, root: usize) {
    let mut largest = root;
    let left = 2 * root + 1;
    let right = 2 * root + 2;

    if left < heap_size && nums[left] > nums[largest] {
        largest = left;
    }

    if right < heap_size && nums[right] > nums[largest] {
        largest = right;
    }

    if largest != root {
        nums.swap(root, largest);
        min_heapify(nums, heap_size, largest);
    }
}