こちらを読むと
- 日本語による疑似コードの書き方が分かります。
- 疑似コードを使えば、最初に考えたアルゴリズムを間違いなくプログラミングできます。
- 記事の所要時間は15分です。
はじめに
プログラミング初心者の方にありがちなのが、いきなりコードを書き始めようとして、どこから書いたらよいか分からない。。。と詰まるパターンかと思います。
本記事では、”疑似コード”というテクニックを使って、日本語で考えた文章⇒プログラムコードに変換する手法をご紹介します！
ステップバイステップでやれば、誰でもプログラムが書けるようになります。
課題：バブルソート
今回、課題として、バブルソートをプログラミングしていくことにします。
アルゴリズムは、こちらが分かりやすいので参照してください。
最終的に、Pythonでコードを書くことを目指します。
それでは、さっそく書いてみましょう！
関数の定義
まずは関数の定義をしましょう。
関数名：バブルソート
引数：ソート対象リスト
戻り値：ソート済みリスト
疑似コードを書く
まずは素直に書いてみましょう。
|
1 2 3 |
バブルソート(ソート対象リスト): バブルソートを行う ソート済みリストを返す |
さすがにこれではプログラムが書けなさそうですね。
バブルソートを分解すると、こんな感じになるでしょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
バブルソート(ソート対象リスト): # 一巡目のソートを行う リストの左端から、隣り合う要素を順番に見ていき、左より右の値が小さければ交換する # 二巡目のソートを行う リストの左端二番目から、隣り合う要素を順番に見ていき、左より右の値が小さければ交換する ... # 最終巡目のソートを行う リストの左端（リストサイズ-2）番目から、隣り合う要素を順番に見ていき、左より右の値が小さければ交換する ソート済みリストを返す |
繰り返しをまとめる
上の、一巡目のソート～最終巡目のソートですが、繰り返し処理ですね。
変数nを使って繰り返しをまとめると、以下のようにできます。
|
1 2 3 4 5 6 |
バブルソート(ソート対象リスト): # 繰り返し、n巡目のソートを行う n=0～リストサイズ-1まで繰り返す リストの左端n番目から、隣り合う要素を順番に見ていき、左より右の値が小さければ交換する ソート済みリストを返す |
最終巡目はリストの最終要素なので、インデックスが0から始まると考えると、”リストサイズ-1″が最終巡目になります。
繰り返し処理の中に入っている、交換処理を具体的に書くとどうなるでしょうか。左と右の要素を交換する処理を、x回繰り返せばよいはずです。よってこうなりますかね。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
バブルソート(ソート対象リスト): # 繰り返し、n巡目のソートを行う n=0～リストサイズ-1まで繰り返す # 交換処理を行う # 1回目 リストの左端n番目とn+1番目を比較し、n+1番目の値が小さければ交換する # 2回目 リストの左端n+1番目とn+2番目を比較し、n+2番目の値が小さければ交換する ... # x回目（n+x = リストサイズ-1） リストの左端n+x-1番目とn+x番目を比較し、n+x番目の値が小さければ交換する ソート済みリストを返す |
交換処理も繰り返しなので、以下のように記述できます。
|
1 2 3 4 5 6 7 8 9 |
バブルソート(ソート対象リスト): # 繰り返し、n巡目のソートを行う n=0～リストサイズ-1まで繰り返す # 繰り返し、交換処理を行う i=0～x-1まで繰り返す。（n+x = リストサイズ-1） # 交換処理を行う リストの左端n+i番目とn+i+1番目を比較し、n+i+1番目の値が小さければ交換する ソート済みリストを返す |
ここで、xが求められるように式を変換しておくと、
n+x = リストサイズ-1
⇔x = リストサイズ-n-1
となります。
ソートの交換処理を具体的に
上記の疑似コードの、”リストの左端n+i番目とn+i+1番目を比較し、n+i+1番目の値が小さければ交換する”の部分に着目します。
少し具体的に書くと、以下のようになります。
|
1 2 3 4 5 6 7 8 |
リストの左端n+i番目とn+i+1番目を比較し、n+i+1番目の値が小さければ交換する に着目 ↓ リストの左端n+i番目を取り出す リストの左端n+i+1番目を取り出す 両者を比較し、n+i+1番目の値が小さければ交換する |
“両者を比較し、n+i+1番目の値が小さければ交換する”の部分があいまいですね。さらに具体的に、交換処理を書いてみましょう。
|
1 2 3 4 5 6 |
リストの左端n+i番目を取り出す リストの左端n+i+1番目を取り出す 両者を比較し、n+i+1番目の値が小さい場合 n+i番目にn+i+1番目を代入 n+i+1番目にn+i番目を代入 ⇒あっ、、n+i番目の値が既に変わってしまっている。。 |
上の方法だと、うまく交換できなさそうですね。
2つの交換処理は、一時的な置き場所を用意すれば、うまく変換できることが知られています。
|
1 2 3 4 5 6 |
リストの左端n+i番目を取り出す リストの左端n+i+1番目を取り出す 両者を比較し、n+i+1番目の値が小さい場合 n+i番目をtmpに記憶 n+i番目にn+i+1番目を代入 n+i+1番目にtmpを代入 |
全てをつなげると、最終的に以下のようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
バブルソート(ソート対象リスト): # 繰り返し、n巡目のソートを行う n=0～リストサイズ-1まで繰り返す # 繰り返し、交換処理を行う i=0～x-1まで繰り返す。（x = リストサイズ-n-1） # 交換処理を行う リストの左端n+i番目を取り出す リストの左端n+i+1番目を取り出す 両者を比較し、n+i+1番目の値が小さい場合 n+i番目をtmpに記憶 n+i番目にn+i+1番目を代入 n+i+1番目にtmpを代入 ソート済みリストを返す |
ここまできたら、もうプログラムにできそうですね！
疑似コード⇒Pythonコードへの変換
最後にPythonのソースコードに変換します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
def bubble_sort(num_list): length = len(num_list) # 繰り返し、n巡目のソートを行う for n in range(length): x = length - n - 1 # 繰り返し1巡：i = 0 ～ x-1 まで繰り返し for i in range(x): if (num_list[i] > num_list[i+1]): tmp = num_list[i] num_list[i] = num_list[i+1] num_list[i+1] = tmp return num_list |
まとめ
- 日本語による疑似コードの書き方が分かりました。
- 疑似コードを使えば、最初に考えたアルゴリズムを間違いなくプログラミングできることが実感できました。
ここまで厳密に疑似コードプログラミングすると時間がかかってしまいます。
よって、明らかな部分は通常のソースコードで書き、不明点を疑似コードで書きながら詰めていくスタイルが現実的でしょう。
しかし、いきなりソースコードを書き始めるよりも、断然プログラムを理解しながら書けると思います。
Reference
以下の書籍、9.2 疑似コードプログラミングプロセス(PPP)に、疑似コードの内容が詳しく書いてあります。
他にもテクニック満載なので、プログラミングが好きな方はチェックしてみてはいかがでしょうか。
