【Python】Bubble Sortを学びながらPythonの基礎を身につける記事

【Python】Bubble Sortを学びながらPythonの基礎を身につける記事



✓目次


Bubble Sortとは

ソートアルゴリズムの一種です。

要素の1番目と2番目を比較し、順番が逆であれば入れ換える。

次に2番目と3番目を比較して入れ換える。

これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。

詳しくは以下のWikipediaを参照ください。

バブルソート - Wikipedia

本記事では、プログラミングにおけるアルゴリズムの練習として、Bubble Sortアルゴリズムを実装したいと思います。

いきなり実装に入る前に、実装する上で必要なpythonの基礎もまとめていきたいと思います。

Pythonの基礎

Bubble Sortをコーディングするために必要な、基本的なPythonの基礎をまずはまとめていきます。

[Python基礎]関数定義

基本的な関数定義としては以下のようなコードがあります。注意点としては、def say_something()前にsay_something()と書いた場合、”関数定義がされてないよ”とエラーになります。pythonは、コードを上から読み込まれるためです。あと()をちゃんとつけましょう。

1
2
3
4
def say_something():
print('hi')
say_something()
# -> hi

ちなみに、print(type(say_something))とすると、say_somethingが何者なのかを確認することができます。

1
2
3
4
def say_something():
print('hi')
type(say_something)
# -> function

返り値を返したい場合は、以下のようにreturnを用います。以下の例だと、shiが入り、返してくれます。

1
2
3
4
5
6
7
def say_something():
s = 'hi'
return s

result = say_something()
print(result)
# -> hi

引数を用いれば、何度もif文を返さなくてOKになるので便利です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def what_is_this(color):
if color == 'red':
return 'tomato'
elif color == 'green':
return 'green pepper'
else:
return "I don't know"

result1 = what_is_this('green')
print(result)

result2 = what_is_this('red')
print(result2)

# -> green pepper
# -> tomato

[Python基礎]関数の引数と返り値の宣言

関数は引数と返り値を明示的に宣言することができます。

1
2
3
4
5
6
def add_nums(a: int, b: int) -> int:
return a + b

r = add_nums(10, 20)
print(r)
# -> 30

ここで、引数にあえてstringを入れてみます。

1
2
3
4
5
6
def add_nums(a: int, b: int) -> int:
return a + b

r = add_nums('a', 'b')
print(r)
# -> ab

結果は、abという文字列を返します。

何を言いたいかというと、関数定義の際に、明示的にa, bにはintを宣言しているにも関わらず、aとbにstringを入れても、pythonはエラーを返してくれません。

この点は気をつけておきましょう。

[Python基礎]関数アノテーション

Python3.0i以降では、関数アノテーションという仕組みが導入されました。

関数の引数や返り値にアノテーション(注釈)となる式を記述することができます。

1
2
3
4
5
6
7
from typing import Union, List

def func_u(x: List[Union[int, float]]) -> float:
return sum(x) ** 0.5

print(func_u([0.5, 9.5, 90]))
# 10.0

あくまでも注釈なので、コードが実行される際に型チェックは行われたりしません。

つまり、アノテーションで指定した型以外の引数を渡してもエラーになりません。

[Python基礎]__name____main__

よく「おまじない」としてスルーされがちなコードですね。

pythonで関数を用いたコードを記述する際に、編集しているpythonファイルが他のコードからimportされて実行されないようにif __name__ = '__main__':を用いることが良しとされています。

作成しているコードが、プロジェクトの一部で使われることが想定される場合、関数を用いる場合は、以下のようにif __name__ = '__main__':を記述して関数を指定しましょう。

1
2
3
4
5
def main():
lesson_package.talk.animal.sing()

if __name__ = '__main__':
main()

詳しくは、Pythonのif name == “main“ とは何ですか?への回答 - Python学習チャンネル by PyQを参照ください。

[Python基礎]内包表記

内包表記は、リストの要素を操作した上で、新しいリストを作成するための記法です。

通常、そのような処理はforやwhileによるループを使用しますが、内包表記を用いると、簡潔に記述することができます。内包表記は、以下の形式で記述します。

  • 新たなリスト = [ 要素への処理 for 要素 in リスト]
  • リスト内の要素を1つ1つ取り出して、要素への処理を実行した上で新しいリストを作成します。
1
2
3
a = [1, 2, 3, 4, 5, 6]
b = [c*3+1 for c in a] # aの要素を3倍して1を足し新たなリストを作る
print(b)

Bubble Sortのコーディング

まずは、数値のlistを扱いたいので、from typing import Listとしておきます。
丁寧にアノテーションでlistを受け付けて、listを返す関数であるということを明示的に示しておきます。先述したとおり、指定した型に従った変数でなくてもエラーは返しません。

1
2
3
from typing import List

def bubble_sort(numbers: List[int]) -> List[int]:

そして、数値のリストを作成し、bubble_sort()に引数として渡してあげます。

1
2
3
4
5
6
from typing import List
def bubble_sort(numbers: List[int]) -> List[int]:

if __name__ == '__main__':
nums = [2, 5, 4, 6, 8, 1]
bubble_sort(nums)

Bubble Sortの仕組みを考慮し、リストのindexの数を取り出したいので、lenメソッドを使い、indexの数を取り出し、それをprintします。

1
2
3
4
5
6
7
8
9
10
from typing import List
def bubble_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
print(len_numbers)

if __name__ == '__main__':
nums = [2, 5, 4, 6, 8, 1]
bubble_sort(nums)

# -> 6

len_numbersを用いてループを回したいので、for文使います。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from typing import List
def bubble_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
print(i)

if __name__ == '__main__':
nums = [2, 5, 4, 6, 8, 1]
bubble_sort(nums)

# 0
# 1
# 2
# 3
# 4
# 5

2つの数字を比較する回数は、今回でいうと6つの数字に対して、5回比較を行うため、len_numbers - 1回行えば良いことがわかります。

さらに、その回数は1回ずつ減っていくことから、len_numbers - 1 -iとすれば良いことがわかると思います。最初iには、0が入り、len_numbersには6が入るので、初期値は5になります。そしてループが回るごとに4, 3, 2, 1、となりますね。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from typing import List

def bubble_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
for j in range(len_numbers - 1 - i):
if numbers[j] > numbers[j+1]:
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
return numbers

if __name__ == '__main__':
nums = [2, 5, 4, 6, 8, 1]
print(bubble_sort(nums))

# -> [1, 2, 4, 5, 6, 8]

もう少し大きな数字でもやってみます。内包表記を用いてlist内部で処理を記述します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from typing import List

def bubble_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
for j in range(len_numbers - 1 - i):
if numbers[j] > numbers[j+1]:
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
return numbers

if __name__ == '__main__':
import random
nums = [random.randint(0, 1000) for i in range(10)]
print(bubble_sort(nums))

# -> [15, 218, 219, 230, 306, 308, 320, 390, 625, 876]

まとめ

本記事では、Bubble Sortというソートアルゴリズムを学びながら、以下のPythonの基礎を学びました。

  • 関数定義
  • 関数の引数と返り値の宣言
  • 関数アノテーション
  • __name__main__
  • 内包表記

アルゴリズムをより詳しく学びプログラミング力を高めたい方

  • 以下の、Udemyのコースがおすすめです。セール時は、1200円で購入可能です。セール時でなくても、講師の方に、Twitterでクーポンコードの発行をお願いすれば、10$(1200円)で受講可能となります。30日間の返金保証もついているので、是非試してみてください。
  • 本記事も、以下のコースで学んだ内容をもとに作成しております。

現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門

現役シリコンバレーエンジニアが教えるPython 3 入門 + 応用 +アメリカのシリコンバレー流コードスタイル

コメント