2022-11-05

"Introduction to Algorithms" を読む 2.1

Insertion sort とループ普遍条件の勉強をした

学生の時に読もうと思ったけど全然読み進められなかったこの書籍に再び挑戦する。読み切れる気は当然しない（読み切ったとしたら 150 記事ぐらい書いたことになる）。

2 章 1 節は Insertion sort である。

Insertion sort の実装

一度 C++ で実装したが、せっかくなのでアルゴリズムの実装には Rust を使うことにした。Rust はまったく書いたことがなかったので、コンパイルエラーに怒られながらなんとか実装できた。間違っていたり、もっとスマートに書ける部分はありそう。

pub fn insertion_sort<T: std::cmp::PartialOrd + Copy>(a: &mut [T]) -> &[T] {
    for j in 2..a.len() + 1 {
        let key = a[j - 1];
        let mut i = j - 1;
        while i > 0 && a[i - 1] > key {
            a[i] = a[i - 1];
            i = i - 1;
        }
        a[i] = key;
    }
    a
}

疑似コードでは配列は 1-index だが、Rust では 0-index である。C++ では int でも添字として使えるが、Rust では添字に usize を使う必要があり、 i32 の変数を添字として使いたい場合はキャストする必要がある。

キャストするのが嫌だったので、配列にアクセスするときはインデックスをひとつ減らすことにした。

Exercises

2.1-1

A = [31, 41, 59, 26, 41, 58] のときのソートの様子を図示せよ。

実装してしまったので、これは実際に動かして確かめてみる。

41 をソート: [31, 41, 59, 26, 41, 58]
ソート後: [31, 41, 59, 26, 41, 58]

59 をソート: [31, 41, 59, 26, 41, 58]
ソート後: [31, 41, 59, 26, 41, 58]

26 をソート: [31, 41, 59, 26, 41, 58]
[31, 41, 59, 59, 41, 58]
[31, 41, 41, 59, 41, 58]
[31, 31, 41, 59, 41, 58]
ソート後: [26, 31, 41, 59, 41, 58]

41 をソート: [26, 31, 41, 59, 41, 58]
[26, 31, 41, 59, 59, 58]
ソート後: [26, 31, 41, 41, 59, 58]

58 をソート: [26, 31, 41, 41, 59, 58]
[26, 31, 41, 41, 59, 59]
ソート後: [26, 31, 41, 41, 58, 59]

[26, 31, 41, 41, 58, 59]

配列だと挿入操作をする際は要素をずらしていく必要がある。途中経過を見ると、要素が左にコピーされていることがわかる。

2.1-2

ソート順序を逆順にするには a[i - 1] > key の比較演算を < にすれば良い。比較するときに同じ値だったらどうするかで「安定」なのかどうかという話になった気がする。

2.1-3

以下のような線形探索問題を考える。

入力：配列 $A$ と値 $v$

出力： $A$ に $v$ が含まれているとき $v = A[i]$ 、含まれていないとき $i = NIL$ となるようなインデックス $i$

ループ普遍条件を使って、自分が考えた線形探索アルゴリズムが正しいかを証明する。

疑似コードを書くとこうなる。うーん、単純。

i = NIL
for j = 1 to A.length
    if A[j] == v
        i = j

ループ普遍条件

$A[1..j]$ に $v$ が存在しないとき $i = NIL$ 、そうでないとき $v=A[i]$ かつ $i <= j$ である。

1. Initialization

$i$ は $NIL$ である。

2. Maintenance

$A[1..j]$ に $v$ が存在しないとき $i = NIL$ である。

$v = A[j]$ のとき $i = j$ である。

3. Termination

$A[1..n-1]$ に $v$ が存在しないとき $j=NIL$ である。

そうでないとき、 $v = A[j]$ である。

書いてみたのはいいものの、あんまりわかってない。

正直あんまりわかってない。

2.1-4

$n$ -bit の数値 $A, B$ の和を計算する。数値は長さ $n$ の配列によって表される。

c = 要素がすべて 0 で長さが (n + 1) の配列
for i = n to 1
    sum = a[i] + b[i] + c[i + 1]
    c[i + 1] = round(sum / 2) // 小数点以下を切り捨て 
    c[i] = sum % 2

こんな感じかなぁ。

3 + 7 で動きをシミュレーションしてみる。

n = 3, a = [0, 1, 1], b = [1, 1, 1], c = [0, 0, 0, 0] である。

配列は 1-index である。

i = n = 3

\begin{align} sum & = a[3] + b[3] + c[4] \nonumber \\ & = 1 + 1 + 0 \nonumber \\ & = 2 \nonumber \end{align}

c = [0, 0, 1, 0]

i = n - 1 = 2

\begin{align} sum & = a[2] + b[2] + c[3] \nonumber \\ & = 1 + 1 + 1 \nonumber \\ & = 3 \nonumber \end{align}

c = [0, 1, 1, 0]

i = n - 2 = 1

\begin{align} sum & = a[1] + b[1] + c[2] \nonumber \\ & = 0 + 1 + 1 \nonumber \\ & = 2 \nonumber \end{align}

c = [1, 0, 1, 0]

結果

$c = 1010_2 = 10_{10}$

$3 + 7$ の計算ができている。

感想

内容は Insertion sort、ループ普遍条件、疑似コード。ループ普遍条件に関してまったく知識がない。もしかすると初めて聞いたのかもしれない。Exercises で条件を書いてみたが、あっている自信はない。

Insertion sort はソートの中でもわかりにくいと思っている。個人的にはソートといえば Bubble sort。