序
配列などで知られる線形データ構造とそれを用いた2つのアルゴリズムを紹介します。
線形データ構造とは
線形データ構造はデータの要素が規則性をもった線形の連なりを成している構造のことです。
最初と最後の要素以外には、一つ前と一つ後の要素がある状態です。
例としては配列、キュー、スタックなどなどがこれに該当します。
配列（Array）
配列はもっとも単純な線形データ構造のひとつです。
n個の同じ型のデータがメモリ上に連続して保持される構造です。
配列の中の要素には指数(index)で扱うことができます。
多くのプログラミング言語においてその指数は0からn-1の間の実数値になっています。
配列の中にあるどの位置の要素であろうと新しい値を代入するのにかかる時間に違いはあまりありません。
連結リスト(Linked List)
連結リストは0あるいはそれ以上の数のノードと呼ばれるデータ要素を保持しています。
ノードにはデータ要素の他に1つあるいは2つのポインタと呼ばれる同連結リスト内の他のノードを指すリンクが保持されています。次あるいは前に繋がるノードが内場合にはnullのポインタが保持されます。
連結リストには
- 片方向 (single linked list)
- 双方向 (double linked list)
の2つがあり、片方向の場合は次ノードへのリンクのみで、最後のノードのリンクがnullになります。
双方向の場合は次ノードと前ノードへのリンクがあり、先頭には前ノードのリンクがnullで、最後のノードのリンクがnullになります。
ポインタによって次のノードの位置を定義しておかなければならない、ということは連結リストの各要素はメモリ上に連続して保持されていないということになります。
連結リストは動的なデータ構造で、その長さは要素の数と等しくなります。
配列と連結リストの違い
連結リストと配列のどちらもリストというより抽象的なデータ構造の実装に使えます。リストは順序をもって連なったデータ構造です。リストを実装するうえで、以下の機能が求められます。
- 要素へのアクセス
- 要素の検索
- 要素の追加
- 要素の削除
しかし連結リストと配列では機能の効率性において違いがあります。
要素へのアクセス
$i$番目のデータにアクセスする場合
配列なら指数$i$をもって参照するだけですが、連結リストの場合は$i-1$に至るまで連結リスト内のノードを辿っていく必要があります。
要素の検索
配列内のとある要素を検索したい場合
配列では一つ一つ参照して比較するか、配列がソートされている場合はのちに解説する二分探索によって探すことができます。
連結リストではノードを順に辿って比較していく必要があります。
要素の追加
ある要素をリストの先頭に追加したい場合
配列では配列内の既存の要素すべてをまず移動させてから、新しい値を先頭においた配列に移動し直さなければならないため、要素の数が多くなってくればくるほど非効率的になっていきます。
連結リストにおいては既存の先頭ノードを次へのリンクにした要素を追加するだけなのでとても効率的です。
要素の削除
ある要素をリストから削除したい場合
配列では削除後の残っている要素すべて移動させる必要があるため、要素数が多くなればなるほど非効率的です。
連結リストにおいては移動の必要がありませんが、ノードを辿って削除するノードの前後のノードのポインタを書き換える必要があります。
スタック(stack)
スタックは要素が連なって保持されているという抽象的なデータ構造ですが、その一番上の値にしか参照できません。
要素を追加する場合は一番上に追加され、削除する場合は一番上が追加されます。だるま落としのように積まれていく感じですね、横から叩けませんが。
スタックはLIFO(後入れ先出し法)のデータ構造と呼ばれるものです。
スタックは配列や連結リストで実装できるデータ構造ですが、一番上以外の値を直接参照することができません。
僕もまだアルゴリズムは勉強中でそんなに例はぱっと出てきませんが、例えばエディタにおけるUndoのシステムや、数式やプログラミング言語におけるインデントや丸括弧、波括弧、引用符などが閉じられているかの確認する関数などで使われていると思います。
キュー(Queue)
キューは要素が連なって保持されているという抽象的なデータ構造で、要素の追加は最後に追加され、削除や参照は先頭から行われるというものです。キューの名の通り、店の前の行列などが例ですね。
キューに値を追加することをenqueue、削除することをdequeueと言います。
キューは配列や連結リストで実装できるデータ構造で、スタック同様、途中の要素に直接参照する事ができないものです。
例としてはCPUのスケジューリングやIOバースト処理などでしょうか。
線形データ構造の検索アルゴリズム
検索アルゴリズムは比較によって成り立っています。
求められる役割としては求められた値が存在するか、あるいは求められた値をキーとした要素を探すかです。
今回は木構造を用いたアルゴリズムを行いません、あくまで線形データ構造の検索アルゴリズムです。
最も有名な検索アルゴリズムには以下の2つがあります。
- 線形探索 (Linear Search)
- 二分探索 (Binary Search)
線形探索 (Linear Search)
線形探索は端的に言って総当り方式 (Brute force)になります。
総当りとはデータ構造の端から求められた値が見つかるか、最後に至るまで求められた値との比較を行うアルゴリズムです。
データ構造の要素が順に並んでいない場合は線形探索しか選択肢がありません。
このアルゴリズムにおける最悪のシナリオは求められた値がデータ構造の最後の要素に至るまで見つからない場合です。
擬似コード
ALGORITHM~LinearSearch(A[0..n-1], ~K)\\
i~\leftarrow~0\\
While~i<n~AND~A[i]\neq K~do\\
i = i + 1\\
if~i <n~return~i\\
else~return~-1
分析
このアルゴリズムにおいて最も頻繁に行われる処理は$A[i]\neq K$ですので、これが最も基礎的な処理になりますが、先に$i<n$があるのでこれが真となるときにはこの基礎処理は行われません。
上記したように最悪のシナリオは求められた値がデータ構造の最後の要素、あるいはそもそも存在しない場合ですのでそれは漸近記法ではこうなります。
C_{worst}(n)=n\in O(n)
二分探索 (Binary Search)
二分探索は分割統治法(Decrease and conquer)にあてはまります。問題が大きく困難な場合に小さな規模に分けていくものです。
この探索法はデータ構造がソートされている場合にしか行なえません。
手順としましては、データ構造を真ん中で分けて半分の片方から探していきます。その時点で最初の値で見つかれば探索は終了です。なければもう片方を見るという形です。
半分のうち最初ではない位置の中に求められている要素があった場合、半分の構造をさらに半分にして、その片方から探していきます。この分割を最後の一つになるまで繰り返していきます。
擬似コード
ALGORITHM~BinarySearch(A[0..n-1], K)\\
i\leftarrow 0,~j\leftarrow n-1\\
while~i\leq j~do\\
m\leftarrow (i+j)/2\\
if~K=A[m]~return~m\\
else~if~K<A[m]~j\leftarrow m-1\\
else~i\leftarrow m+1\\
return~-1
分析
二分探索においても最悪のケースは計3つに分かれている処理と2つの条件分岐が最も多く行われる場合です。
その場合は漸近記法では
C_{worst}(n) = \log_2 n + 1 \in O(\log n)
となります。
ソート
線形データ構造を用いたアルゴリズムには要素を求められた順序に並び替えをするソートがあります。
ソートにおける基本的な命令は多くの場合順序の入れ替えになります。
安定ソート(Stable sort)
たとえば五十音順に並んだ人々が背の順で整列しなおした場合、同じ身長の人間が五十音で前後が決まったままになる、そのようなソート前の状態を保持したソートアルゴリズムを安定ソートと呼びます。
挿入ソート
挿入ソートは安定ソートです。
並び替え用のデータ構造を用意して、並び替え前の構造から比較を用いて正しい位置に値を挿入していく方法です。
擬似コード
ALGORITHM~InsertionSort(A[0..n-1])\\
for~i \leftarrow 1~to~n \leftarrow n-1~do\\
v \leftarrow A[i]\\
j \leftarrow i - 1\\
while~j \geq 0 ~and~A[j] > v ~do\\
A[j+1] \leftarrow A[j] \\
j \leftarrow j-1 \\
the~operation~below~after~while~loop \\
A[j + 1] \leftarrow v
分析
比較である$A[j] > v$が最も多くなるデータ構造が最悪計算時間となります。
C_{worst}(n)={\sum_{i=1}^{n-1}}{\sum_{j=0}^{i-1}}1 = {\sum_{i=1}^{n-1}i} = \frac{(n-1)n}{2} \in O(n^2)
選択ソート(Selection Sort)
選択ソートは安定ソートではありません。
データ構造の最小の値をその時点でのデータ構造の先頭の値と入れ替えることで並び替えをするアルゴリズムです。
擬似コード
ALGORITHM~SlectionSort(A[0..n-1])\\
for~i \leftarrow 0~to~n-2~do\\
minimum \leftarrow i\\
for~j \leftarrow i+1~ton-1~do\\
if~A[j] < A[minimum]~minimum \leftarrow j \\
the~operation~below~after~inner~for~loop\\
swap A[i]~and~A[minimum]
分析
このアルゴリズムではどのようなデータ構造であっても$A[j] < A[minimum]$の比較を行うので計算時間に違いはありません。
C(n) = {\sum_{i=0}^{n-2}}{\sum_{j=i+1}^{n-1}}1 = {\sum_{i=0}^{n-2}}(n-1-i) = \frac{(n-1)n}{2}
バブルソート
この手法は隣り合う要素を比較しあっていくことで整列させるアルゴリズムで安定したソートでもあります。
擬似コード
ALGORITHM~BubbleSort(A[0..n-1])\\
for~i\leftarrow 0~to~n-2~do\\
for~j\leftarrow 0~to~n-2-i~do\\
if~A[j+1] < A[j]~swap~A[j]~and~A[j+1]
分析
このアルゴリズムにおける最悪計算時間は$A[j+1] < A[j]$の比較が最も多く行われる場合です。
\begin{align}
C_{worst}(n)={\sum_{i=0}^{n-2}}{\sum_{j=0}^{n-1}}1 = {\sum_{i=0}^{n-2}}\{(n-2-i)-0+1\}\\
={\sum_{i=0}^{n-2}}(n-1-i) = \frac{(n-1)n}{2} \in O(n^2)
\end{align}
マージソート
二分探索と同じ分割統治法のアルゴリズムです。大きな問題を同様の小さな問題に分割して解決して統合されるものです。
マージソートは分割と統合の２つのプロセスに大きく分けられます。
擬似コード
統合するアルゴリズム
ALGORITHM Merge(A[i...j], m)
//mはメジアンで配列を中央で二分割するための指数
//T[i...j]は一時的な配列
p <- i;
q <- m + 1;
r <-i;
while p <= m and q <= j do{
if A[p] <= A[q]{
T[r] <- A[p]
p <- p + 1
} else {
T[r] <- A[q]
q <- q + 1
}
r <- r + 1
}
if p <= m {
T[r...j] <- A[p...m]
}
if q <= j {
T[r...j] <- A[q...j]
}
A[i...j] <- T[i...j]
分割するアルゴリズム
ALGORITHM Mergesort(A[i...j])
if i < j{
m <- (i+j)/2
Mergesort(A[i...m])
Mergesort(A[m+1...j])
Merge(A[i...j], m)
}
分析
時間的効率性でいうと最悪計算時間は$C_{worst} \in O(n~log~n)$になります。
空間的効率性でいうと一時的な空間が必要になります。
安定ソートです。
クイックソート
分割統治法のアルゴリズムで２つのアルゴリズムに分けて行われます。
分割アルゴリズム
ALGORITHM Partition(A[l...r])
//Pは配列の最初の値でこれを軸とする
//入力される値は配列A[0...n -1]の部分配列でlは左、rは右を意味する
//出力する値は配列を２つに分けるための分割点の値を返す
p <- A[l]
i <- l
j <- r + 1
repeat{
repeat i <- i + 1 until A[i] >= p
repeat j <- j - 1 until A[j] <= p
swap(A[i], A[j])
} until i >= j
swap(A[i], A[j])
swap(a[l], A[j])
return j
クイックソートアルゴリズム
ALGORITHM Quicksort(A[l...r])
//部分配列をクイックソートする
//s は分割点
if l / r {
s <- Partition(A[l...r])
Quicksort(A[l...s - 1])
Quicksort(A[s + 1...r])
}
分析
時間的効率性では最悪計算時間が$C_{worst} \in O(n^2)$
平均計算時間が$C_{avg} \in (n~log~n)$
空間的効率性では一時的な空間が必要ではありません
安定ソートではありません
備考
アルゴリズムの基礎と擬似コード、分析については僕が以前書いたこちら