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

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

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

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

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

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

挿入法（バラバラのデータを昇順か降順に並べらえる方法の１つ）【ソート１】
マージソート(Merge Sort)【ソート２】
クイックソート【ソート３】
バブルソート【ソート4】
ヒープソート【ソート5】
逐次探索アルゴリズム【サーチ１】
二分探索法（バイナリサーチ）【サーチ２】
ハノイの塔
参考文献

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

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

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

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

リストA	3	1	2	9	1
j=1	3	1	2	9	1
j=2（を実行した結果）	1	3	2	9	1
j=3	1	2	3	9	1
j=4	1	2	3	9	1
j=5	1	2	3	1	9
j=4(=5-1)	1	2	1	3	9
j=3(=5-1-1)	1	1	2	3	9

例えばこんな感じ

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

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

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

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

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

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

リスト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番目にもう小さい値が来たので１つ右のマスでまた次の小さい値を受け取る準備）
 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

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

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

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

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

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

二分探索法（バイナリサーチ）【サーチ２】

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

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

リスト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（行き先、目的地）です。

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

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