数式で理解するソートアルゴリズム

ここでは、ソートアルゴリズムを数式を使って解説する。ソートアルゴリズムの解説では、手順を追って説明することが多い。ここでは、数式を使ってソートアルゴリズムを解説していく。

では、さっそく以下に解説していく

入力

入力として以下の順不同な長さnの入力が与えられる。 $$ a_8, a_2, a_1, …, a_k = b_1, b_2, … , b_k, .. , b_n=B $$ $$ (1 \leq k \leq n, \quad len(B)=n) $$ これを昇順に並び替えることがゴールである。数式で表すと以下の通り。

ゴール

$$ a_1, a_2, …, a_k, .. a_n $$ $$ (a_k \leq a_{k+1}, \quad 1\leq k\leq n )$$

選択ソート

数式による解説

$$ REP_{i=1}^n swap(b_i, \argmin_{b_k}[b_i, b_{i+1}, …, b_k,…,b_n]) $$ ここで、$REP_{i=1}^n$は、iを1からnまで繰り返すことを意味する。

文字による解説

選択ソートは配列の中から最小値を探し、ソート済み配列に格納することを繰り返すことによりソートを行う手法のことである。

バブルソート

数式による解説

$$ REP+{i=0}^{n-1}REP-{j=n-1}^{i+1} \begin{cases} swap(b_j,b_{j-1}) & (if \quad b_j < b_{j-1}) \ nothing & (else) \end{cases} $$ ここで、$REP+{i=0}^n$は、iを１ずつ加算していきiが0からnをなるまで繰り返すことを意味する。$REP-{j=n-1}^{i+1}$は、jを1ずつ減算していきjがn-1からi+1になるまでまで繰り返すことを意味する。

文字による解説

隣り合う要素の大小を比較しながらソートを行う手法である。

挿入ソート

数式による解説

$$ REP+{i=1}^{n-1}{REP-{j=i-1}^{j \geq 0 \ && \ b_j \gt b_i} {b_{j+1} \leftarrow b_j} \ b_{j+1} \leftarrow b_i } $$ ここで、$REP+{i=1}^{n-1}$は、iを1からn-1まで繰り返すことを意味する。$REP-{j=i-1}^{j \geq 0 \ && \ b_j \gt b_i}$は、jがn-1から$j \geq 0 \ && \ b_j \gt b_i$を満たすまで繰り返すことを意味する。

文字による解説

隣り合う要素の大小を比較しながらソートを行う手法である。