3つの基本ソートをIPA式疑似言語に
3大ソートを日本語からIPA疑似言語へ
このワークでやること
これまでに、
- バブルソート
- 選択ソート
- 挿入ソート
を、自分の手で実際に並べ替えました。
ここからは、手でやった処理を
日本語で確認する
↓
必要な情報に名前を付ける
↓
IPAの疑似言語へ直す
という順番で表現していきます。
この授業では、配列の要素番号は 0から始まるものとします。
data[0]
data[1]
data[2]
...
2つの値を交換するときは、
swap(data[a], data[b])
のように表します。
1．バブルソート
1-1．まず、日本語でアルゴリズムを確認しよう
次の空欄を埋めてください。
① 配列の左端から、右方向へ順番に調べる。
② 一度に比較するのは、隣り合った ________ 個の値である。
③ 左の値が右の値より ________ とき、
2つの値を交換する。
④ 1回の比較が終わったら、
比較する位置を右へ ________ 個分進める。
⑤ 右端まで調べたら、1周終了する。
⑥ 1周だけでは並び終わらないので、
同じ処理を何周も繰り返す。
1-2．「今見ている位置」に名前を付けよう
例えば、次のように比較していました。
data[0] と data[1]
data[1] と data[2]
data[2] と data[3]
...
左側の要素番号は、
0 → 1 → 2 → ...
と1ずつ増えています。
この、
今見ている位置
を i とします。
今見ている位置 → i
すると、隣り合った2つの値は、
data[＿＿＿＿] と data[＿＿＿＿]
と表せます。
1-3．1回の比較を疑似言語にしよう
日本語では、
左側の値の方が大きければ、2つの値を交換する。
でした。
これを疑似言語に直してください。
if (＿＿＿＿＿＿＿＿ ＞ ＿＿＿＿＿＿＿＿)
swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
endif
1-4．1周分を疑似言語にしよう
1周の間、比較する位置 i は、
0 → 1 → 2 → 3 → ...
と変化します。
要素数を n とすると、最後に比較するのは、
data[n - 2] と data[n - 1]
です。
したがって、i は
0 から ＿＿＿＿＿＿ まで
変化します。
1周分の疑似言語を完成させてください。
for (i を ＿＿＿＿ から ＿＿＿＿＿＿ まで 1 ずつ増やす)
if (＿＿＿＿＿＿＿＿ ＞ ＿＿＿＿＿＿＿＿)
swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
endif
endfor
1-5．何周も繰り返す処理を作ろう
1周だけでは、すべての値が並ぶとは限りません。
そこで、
何周目か
を表す変数を j とします。
何周目か → j
要素が n 個なら、最大で n - 1 周すれば並びます。
j は0から始めるので、
0 から ＿＿＿＿＿＿ まで
繰り返せばよいことになります。
バブルソート全体を完成させてください。
○bubbleSort(整数型の配列: data)
整数型: n ← dataの要素数
整数型: i, j
for (j を ＿＿＿＿ から ＿＿＿＿＿＿ まで 1 ずつ増やす)
for (i を ＿＿＿＿ から ＿＿＿＿＿＿ まで 1 ずつ増やす)
if (＿＿＿＿＿＿＿＿ ＞ ＿＿＿＿＿＿＿＿)
swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
endif
endfor
endfor
1-6．完成形を確認しよう
完成形を見る
○bubbleSort(整数型の配列: data)
整数型: n ← dataの要素数
整数型: i, j
for (j を 0 から n － 2 まで 1 ずつ増やす)
for (i を 0 から n － 2 まで 1 ずつ増やす)
if (data[i] ＞ data[i ＋ 1])
swap(data[i], data[i ＋ 1])
endif
endfor
endfor
2．選択ソート
2-1．まず、日本語でアルゴリズムを確認しよう
次の空欄を埋めてください。
① 左側には、すでに位置が確定した値が並んでいる。
② まだ確定していない部分の中から、
一番 ________ 値を探す。
③ 一番小さい値を見つけたら、
その値そのものではなく、値がある ________ を覚えておく。
④ 最後まで探し終わったら、
見つけた最小値と未確定部分の一番 ________ の値を交換する。
⑤ 交換後、「確定済みの個数」を ________ 増やす。
⑥ これを、未確定部分が残っている間繰り返す。
2-2．「確定済みの個数」に名前を付けよう
例えば、
1 2 | 7 4 6 3 5
のような状態なら、
1 2
の2個は、すでに位置が確定しています。
そこで、
左から何個の位置が確定しているか
を表す変数を fixedCount とします。
確定済みの個数 → fixedCount
上の例なら、
fixedCount = ＿＿＿＿
です。
次に確定させる位置は、
data[＿＿＿＿＿＿＿＿]
です。
2-3．「最小値の位置」に名前を付けよう
選択ソートでは、未確定部分を最後まで調べて、
一番小さい値がどこにあったか
を覚えておく必要があります。
その位置を minPos とします。
一番小さい値の位置 → minPos
探し始める前は、
「今のところ、未確定部分の一番左が最小」
と考えます。
したがって、
minPos ← ＿＿＿＿＿＿＿＿
となります。
2-4．「今調べている位置」に名前を付けよう
未確定部分を左から右へ調べるとき、
今調べている位置
を i とします。
今調べている位置 → i
最初に data[fixedCount] を最小値候補にしているので、
次に調べる位置は、
fixedCount ＋ ＿＿＿＿
です。
最後は、
n － ＿＿＿＿
まで調べます。
2-5．最小値を探す処理を疑似言語にしよう
日本語では、
今調べている値が、
今まで見つけた最小値より小さければ、
最小値の位置を更新する。
でした。
疑似言語を完成させてください。
if (＿＿＿＿＿＿＿＿ ＜ ＿＿＿＿＿＿＿＿)
minPos ← ＿＿＿＿
endif
2-6．未確定部分を最後まで探そう
for (i を ＿＿＿＿＿＿＿＿ から ＿＿＿＿＿＿＿＿ まで 1 ずつ増やす)
if (＿＿＿＿＿＿＿＿ ＜ ＿＿＿＿＿＿＿＿)
minPos ← ＿＿＿＿
endif
endfor
2-7．探し終わったら交換しよう
最小値が見つかったら、
未確定部分の一番左
と、
見つけた最小値
を交換します。
疑似言語を完成させてください。
if (＿＿＿＿＿＿＿＿ ≠ ＿＿＿＿＿＿＿＿)
swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
endif
交換が終わったら、
fixedCount ← fixedCount ＋ ＿＿＿＿
とします。
2-8．選択ソート全体を疑似言語にしよう
最初は、まだ1個も位置が確定していないので、
fixedCount ← ＿＿＿＿
です。
そして、最後の1個を除いて位置を確定させれば、 残った1個の位置も自動的に決まります。
完成させてください。
○selectionSort(整数型の配列: data)
整数型: n ← dataの要素数
整数型: fixedCount, i, minPos
fixedCount ← ＿＿＿＿
while (fixedCount ＜ ＿＿＿＿＿＿)
minPos ← ＿＿＿＿＿＿＿＿
for (i を ＿＿＿＿＿＿＿＿ から ＿＿＿＿＿＿＿＿ まで 1 ずつ増やす)
if (＿＿＿＿＿＿＿＿ ＜ ＿＿＿＿＿＿＿＿)
minPos ← ＿＿＿＿
endif
endfor
if (＿＿＿＿＿＿＿＿ ≠ ＿＿＿＿＿＿＿＿)
swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
endif
fixedCount ← fixedCount ＋ ＿＿＿＿
endwhile
2-9．完成形を確認しよう
完成形を見る
○selectionSort(整数型の配列: data)
整数型: n ← dataの要素数
整数型: fixedCount, i, minPos
fixedCount ← 0
while (fixedCount ＜ n － 1)
minPos ← fixedCount
for (i を fixedCount ＋ 1 から n － 1 まで 1 ずつ増やす)
if (data[i] ＜ data[minPos])
minPos ← i
endif
endfor
if (minPos ≠ fixedCount)
swap(data[fixedCount], data[minPos])
endif
fixedCount ← fixedCount ＋ 1
endwhile
3．挿入ソート
3-1．まず、日本語でアルゴリズムを確認しよう
次の空欄を埋めてください。
① 左から「整列済みの個数」だけ、
小さい順に並んでいるものとする。
② 次に処理するのは、
整列済み部分のすぐ ________ にある値である。
③ その値と、すぐ ________ の値を比較する。
④ 左隣の値が今の値より ________ とき、
2つの値を交換する。
⑤ 交換したら、今の値は配列中を ________ 方向へ1つ移動する。
⑥ これを、左隣の値の方が大きい間繰り返す。
⑦ 1つの値を正しい位置まで入れたら、
「整列済みの個数」を ________ 増やす。
3-2．「整列済みの個数」に名前を付けよう
例えば、
2 5 6 | 1 4 3
なら、
2 5 6
の3個は、すでに小さい順に並んでいます。
そこで、
左から何個が整列済みか
を sortedCount とします。
整列済みの個数 → sortedCount
上の例なら、
sortedCount = ＿＿＿＿
です。
次に処理する値は、
data[＿＿＿＿＿＿＿＿]
です。
3-3．「今動かしている位置」に名前を付けよう
挿入する値は、左隣と交換するたびに1つずつ左へ移動します。
そこで、
今動かしている値の位置
を i とします。
最初は、
i ← ＿＿＿＿＿＿＿＿
です。
3-4．左隣との比較を疑似言語にしよう
交換を続ける条件は2つあります。
・まだ左端まで来ていない
・左隣の値の方が大きい
まず、
左端まで来ていない
は、
i ＞ ＿＿＿＿
と表せます。
次に、
左隣の値の方が大きい
は、
＿＿＿＿＿＿＿＿ ＞ ＿＿＿＿＿＿＿＿
と表せます。
この2つを and でつなぎます。
while ((＿＿＿＿ ＞ ＿＿＿＿) and (＿＿＿＿＿＿＿＿ ＞ ＿＿＿＿＿＿＿＿))
swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
i ← ＿＿＿＿＿＿＿＿
endwhile
3-5．整列済みの範囲を増やそう
1つの値を正しい位置まで入れたら、
sortedCount ← sortedCount ＋ ＿＿＿＿
とします。
最初は、
data[0]
の1個だけなら、必ず整列済みです。
したがって、
sortedCount ← ＿＿＿＿
から始めます。
3-6．挿入ソート全体を疑似言語にしよう
完成させてください。
○insertionSort(整数型の配列: data)
整数型: n ← dataの要素数
整数型: sortedCount, i
sortedCount ← ＿＿＿＿
while (sortedCount ＜ ＿＿＿＿)
i ← ＿＿＿＿＿＿＿＿
while ((＿＿＿＿ ＞ ＿＿＿＿) and (＿＿＿＿＿＿＿＿ ＞ ＿＿＿＿＿＿＿＿))
swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
i ← ＿＿＿＿＿＿＿＿
endwhile
sortedCount ← sortedCount ＋ ＿＿＿＿
endwhile
3-7．完成形を確認しよう
完成形を見る
○insertionSort(整数型の配列: data)
整数型: n ← dataの要素数
整数型: sortedCount, i
sortedCount ← 1
while (sortedCount ＜ n)
i ← sortedCount
while ((i ＞ 0) and (data[i － 1] ＞ data[i]))
swap(data[i － 1], data[i])
i ← i － 1
endwhile
sortedCount ← sortedCount ＋ 1
endwhile
No Comments