疑似コードとは【アルゴリズム紹介】

スポンサーリンク

アルゴリズムさえ理解していれば、具代的な言語は何を使おうがすぐになれるので疑似コードは役に立ちます。

日本語でいろいろ説明して書くのを疑似コードと呼んだり、コンピュータ言語を形式的に省略したものを疑似コードと呼ぶこともありますが、ここでは日本語で書いたものを紹介します。

ちなみに学校のプログラミング授業だと、scratchが多いっぽいですね。

実際に疑似コードを見てみましょう。

ソートは昇順(小さい順)に並べるアルゴリズムを紹介しています。

スポンサーリンク

挿入法(バラバラのデータを昇順か降順に並べらえる方法の1つ)【ソート1】

挿入法ではソート済みの範囲を1個ずつ広げていく

Input:リスト(A)、リストの長さ(n)
Output:リスト

昇順(小さい順)に並べるアルゴリズム

1 for i=1 to n
2  do j ← i
3   while (A[j-1] ≧ A[j] かつ j > 1 )
4    do A[j-1]とA[j]を交換
5     j ← j-1

1つ目の要素(A[1])はとりあえずそのまま。(3行目のj>1を満たさない)
A[2] ≧ A[3] (3個目の要素が小さいor同じ)なら、位置をスイッチする。(4行目)
次は元々3個目だった要素と1個目の要素を比較するのでインデックスを1つ少なくする。(5行目)

リストA31291
j=131291
j=2(を実行した結果)13291
j=312391
j=412391
j=512319
j=4(=5-1)12139
j=3(=5-1-1)11239
例えばこんな感じ

最良計算時間O(n)
最悪計算時間O(n2)

マージソート(Merge Sort)【ソート2】

再帰という手法を用いています。

Sort(A, i , j ) //A[i]からA[j]をソートするプログラム

1 if(i == j) then return A[i];
2 else
3  m = (i+j-1)/2
4  return(Merge(Sort(A, i ,m), Sort(A, m+1 , j));

Merge(L, R)はソート済みの配列L, Rを併合(merge)してソート済み配列を返す関数。↓はMerge(L,R)のアルゴリズム

初期化:j←1, k←1
各i=1,2,...,aに対して(配列Aの長さがa)
 if L[i] < R[k] //今のLの最小値とRの最小値を比較
 then A[i]←L[i], i←i+1, j←j+1
 else A[i]←R[i], i←i+1, k←k+1

クイックソート【ソート3】

適当に自然数(これをピボと呼ぶ)を選んで、リストの番号がそれ以下・それ以上で分けて再起的にソートしていきます。

リストAの長さがnとして、
最初はQuickSort(A,1,n)を呼び出します。

QuickSort(A,p,r)(q番目からr番目をソートする)
 if p < r(ピボ)
  then q ← Partition(A,p,r)(新しいピボの位置を決定)
       QuickSort(A,p,q-1)(ピボより前の部分)
       QuickSort(A,q+1,r)(後ろの部分)
Partition(A,p,r)(パーテーションを作る)
 ピボ ← A[r]
 i ← p-1
 for j ← p to r-1
  do if A[j] ≦ ピボ(j番目が基準値より大きいならそのまま。小さいなら、)
   then A[i+1]とA[j]を交換(小さいj番目はi+1番目に移動)
        i ← i+1(i+1番目にもう小さい値が来たので1つ右のマスでまた次の小さい値を受け取る準備)
 A[i+1]とA[r]を交換
 return i+1 //ピボの位置を返す(A[p~ピボの位置]≦A[ピボの位置]≦A[ピボの位置~r] になっている)(パーテーションが作れた)

説明を省略した版↓

QuickSort(A,p,r)
 if p < r(ピボ)
  then q ← Partition(A,p,r)
       QuickSort(A,p,q-1)
       QuickSort(A,q+1,r)
Partition(A,p,r)
 ピボ ← A[r]
 i ← p-1
 for j ← p to r-1
  do if A[j] ≦ ピボ
   then A[i+1]とA[j]を交換
        i ← i+1
 A[i+1]とA[r]を交換
 return i+1 //ピボの位置を返す

バブルソート【ソート4】

最初から順番に見ていく、最もシンプルなソートと言えそうです。

for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
end for

return list

ヒープソート【ソート5】

半順序木を作り、それを整列させるアルゴリズム。

function heapsort(input, count)
    heapify(a,count)
    end <- count - 1
    while end -> 0 do
    swap(a[end],a[0])
    end<-end-1
    restore(a, 0, end)

function heapify(a, count)
    start <- parent(count - 1)
    while start >= 0 do
        restore(a, start, count - 1)
        start <- start - 1

逐次探索アルゴリズム【サーチ1】

先頭から順番に見つけたい値が見つかるまで1つ1つ探す単純なアルゴリズム。

Input:配列A、探したい値g
Output:探したい値は何番目にあるか

index = -1 // 目的の値が見つからないときは -1番目として返す

for n 
 if A[n] == g
  index = n

二分探索法(バイナリサーチ)【サーチ2】

この方法はデータが既にソートされている(昇順か降順に整列している)必要がある。

「4」はリストの何番目に入っているか、とかが分かる。

リストAの大きさ(長さ)がn
left = 1
right = n

while(left ≦ right)
 center = (left + right)/2
 if A[center] == 位置を知りたい値
  center番目にあるよと出力
 else if A[center] < 位置を知りたい値
  left = center + 1(探す範囲を右に寄せる)
 else
  right = center - 1

ハノイの塔

円盤の数はnとします。

再帰を使うと簡単に書けます。

destはdestination(行き先、目的地)です。

3つ塔があって、一番左に円盤があるとします。
最終的には、真ん中の塔に移すとします。

Hanoi(n,from,dest,work)
    if(n>=1)
        Hanoi(n-1,from,work,dest);(3番目の塔に一番大きい円盤以外を移す)
        一番大きい円盤を真ん中に置く
        Hanoi(n-1,work,dest,from);(3番目の塔にあるn-1個の円盤を真ん中に移す)

参考文献

情報システム基盤学基礎1
http://www.sd.is.uec.ac.jp/koga/lecture/FSkiso1/kiso1_02.pdf

コメント

タイトルとURLをコピーしました