高等学校 情報Iの要点 コンピュータとプログラミング後編 #8

リュディアです。引き続き高等学校 情報Iの要点 コンピュータとプログラミング後編 をまとめていきます。

高等学校 情報Iの要点 コンピュータとプログラミング後編のまとめへのリンクをまとめておきます。

今回はソートと呼ばれるアルゴリズムについて考えてみます。ソートとは並べ替えという意味です。探索と比較するとソートは動きが複雑です。もし難しいようならアルゴリズムの内容まで理解できなくてもよいと思います。ここでは有名な選択ソートとクイックソートを見てみます。まず選択ソートからです。ソート対象となるデータは以下の整数のリストを用います。

a = [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

最初に Python でソートをしたいだけ、つまり自分でソートを実装しない場合の例をあげます。

a = [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
print("Before sorting", a)

a.sort()

print("After sorting", a)

実行結果

Before sorting [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
After sorting [1, 2, 4, 5, 7, 8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]

簡単ですね。Before sorting のデータは元のままですが、After sorting のデータは小さい数から大きい数に向けてソートされていますね。多くの場合はこの方法で構わないのですが、今回はソートの勉強と思って実際にソートを行う処理を Python でプログラミングしてみます。選択ソートからです。以下の例を見てください。

def selectionSort(a):
 for i in range(0,len(a),1):
   for j in range(i+1,len(a),1):
     if a[j] < a[i]:
       tmp = a[i]
       a[i] = a[j]
       a[j] = tmp

a = [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
print("Before sorting", a)

selectionSort(a)

print("After sorting", a)

実行結果

Before sorting [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
After sorting [1, 2, 4, 5, 7, 8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]

もちろんソートはできているのですが、ここではソートの内部を理解することが重要です。仕組みは2重の反復処理によりリストの中から最小のものを探して選択、選択したものを除外して次に小さいものを選択しソートを完了します。直感的なアルゴリズムですが効率は悪いです。

次にクイックソートです。こちらは選択ソートと比べると効率が良いです。こちらも Python のプログラムを見てみましょう。再帰呼び出しという自分自身を使う関数を定義しています。

def quickSort(a, start, end):
 m = int((start+end)/2)
 i = start
 j = end
 while(i<j):
   while a[i] < a[m]:
     i = i+1
   while a[j] > a[m]:
     j = j-1
   if i>=j:
     break
   temp = a[i]
   a[i] = a[j]
   a[j] = temp
   if i==m:
     m = j
   elif j==m:
     m = i
   i = i+1
   j = j-1
   if start < i-1:
     quickSort(a, start, m-1)
   if end > j+1:
     quickSort(a, m+1, end)

a = [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
print("Before sorting", a)

quickSort(a, 0, len(a)-1)

print("After sorting", a)

実行結果

Before sorting [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
After sorting [1, 2, 4, 5, 7, 8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]

クイックソートは以下のように振る舞います。
1. 基準値を1つ選択する
2. 基準値より小さいグループと大きいグループの2つにグループわけ
3. 2つのグループのそれぞれで再度基準値を1つ選択し、2を繰り返す。
4. 以下、グループわけで要素が1つになるまで繰り返しソート完了

探索のときと同じく時間計算量と考え方を導入してみます。N個のデータをソートする場合を考えて、Nは大きな数であるとします。このとき選択ソートは最悪の場合 N * N = Nの2乗回の反復が必要となる可能性があります。しかしクイックソートは N * log(N)の反復で抑えることができるので要素数 N が大きい場合は実行時間に大きな差が出ます。

すこし難しかったかもしれません。内容が難しかった方はソートするだけであれば内容はわからなくてもよいと現段階では割り切ってもいいと思います。

では、ごきげんよう。