学生向けプログラミング入門

学生向けにプログラミングを解説。Java、C++、Ruby、PHP、データベース、Ruby on Rails, Python, Django

Python | 10 | 並び替えプログラム

<<前  [TOP]  次>>


並び替えには、いろいろな方法がありますが、まずは最も簡単な方法を紹介します。
次のプログラムを作ってみましょう。


【sort1.py】

# sort1.py

data = [10, 75, 24, 32, 98, 72, 88, 43, 60, 35, 54, 62, 2, 12, 82]

for i in range(0,len(data)):
	max = data[i]
	maxIndex = i

	for j in range((i+1),len(data)):
		if (data[j] > max) :
			max = data[j]
			maxIndex = j
		else:
			max = data[i]
			maxIndex = i			

		data[maxIndex] = data[i]
		data[i] = max

for i in range(0,len(data)):
	print( str(i+1) + ':' + str(data[i]))



このプログラムは二重ループを使って隣同士の数字の大きさを比べます。
数字が大きければその数字を最大値とおいてまた隣同士を比べます。


まず、最初のfor文で次の様に記述しています。

max = data[i]

ここで i は最初 0ですから、配列データのdata[0]=10を示しています。
max=10としているわけです。


そのまま次のfor文に入り、data[j]とmaxを比べていきます。
ここで j はj = i + 1なので、j = 1となりますから、配列データのdata[1]=75を示しています。


10と75を比べれば当然75の方が大きいので、if文の条件に当てはまり、次の処理が行われます。

max =data[j]

ここで今、 data[j] は75のことですから、max=75となりました。
そのまま、このループは続き75と24,75と32、75と98と言う感じで順番に大きさを比べていきます。
75と98を比べた時点で、maxは98となりました。
98より大きな数字はないので、max=98のままこの内側のループを抜けます。
そこで、次の処理が行われます。

data[maxIndex] = data[i]
data[i] = max

ここで、maxIndexは98のインデックスを指しますから、data[4] = 98より、MaxIndex=4となっているはずです。
代入して書き直すと次のようになります。

data[4] = data [0]
data[0] = 98

この処理により、data[4]にdata[0]の10が代入され、data[0]にはmaxの98が代入されました。


今の時点で配列は次のように変わりました。

data = [ 98, 75, 24, 32, 10, 72, 88, 43, 60, 35, 54, 62, 2, 12, 82 ]

そして、また最初のfor文に戻り、今度はi=1となるのでmaxは75で内側のループに入り、隣と大きさを比べていく処理を繰り返します。


最後もfor文で結果を出力しています。
出力結果です。

sort1.py
sort1.py



次のプログラムを作ってみましょう。


【sort2.py】

# sort2.py

data = [10, 75, 24, 32, 98, 72, 88, 43, 60, 35, 54, 62, 2, 12, 82]

tmp=0

for i in range(0,len(data)-1):

	for j in range(0,len(data)-(i+1)):

		if (int(data[j]) < int(data[j+1])) :
			tmp = data[j]
			data[j] = data[j+1]
			data[j+1] = tmp

for i in range(0,len(data)):
	print( str(i+1) + ':' + str(data[i]))



この並べ替えのプログラムは、隣同士の大きさを比べて大きかったらひっくり返すといった処理をひたすら繰り返し並び替えるといった手法をとっています。
バブルソートと呼ばれています。
sort1.pyよりも少ない処理回数で並び替えることができます。


内側のループのif文を見てください。

int(data[j]) < int(data[j+1])

まずint()関数を使って整数にして、大きさを比べています。
右側の数字の方が大きかったらまずtmpという変数に小さい方の数字を代入しています。
次に、小さい数字のあった場所に大きい方の数字を代入します。
最後に、大きい方の数字があった場所にtmp(小さい方の数字)を代入します。
この作業を、一番左から順に(今回の場合は10)最後まで行います。
最後までいったらまた、最初のfor文まで戻りまた左から順にひっくり返していきます。


内側のfor文が[ len(data)-i-1 ]回しかループしていないので、その分sort1.pyよりこちらの方が効率が良いと言えます。


出力結果です。

sort2.py
sort2.py



<<前  [TOP]  次>>