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

当ページのリンクには広告が含まれています。

✓目次

• Bubble Sortとは
• Pythonの基礎
  • [Python基礎]関数定義
  • [Python基礎]関数の引数と返り値の宣言
  • [Python基礎]関数アノテーション
  • [Python基礎]__name__と__main__
  • [Python基礎]内包表記
• Bubble Sortのコーディング
• まとめ

Bubble Sortとは

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

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

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

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

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

バブルソート - Wikipedia

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

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

Pythonの基礎

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

[Python基礎]関数定義

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

def say_something():
    print('hi')
say_something()
# -> hi

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

def say_something():
    print('hi')
type(say_something)
# -> function

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

def say_something():
    s = 'hi'
    return s

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

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

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基礎]関数の引数と返り値の宣言

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

def add_nums(a: int, b: int) -> int:
    return a + b

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

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

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以降では、関数アノテーションという仕組みが導入されました。

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

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__':を記述して関数を指定しましょう。

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つ取り出して、要素への処理を実行した上で新しいリストを作成します。

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を返す関数であるということを明示的に示しておきます。先述したとおり、指定した型に従った変数でなくてもエラーは返しません。

from typing import List

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

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

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します。

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文使います。

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、となりますね。

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内部で処理を記述します。

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日間の返金保証もついているので、是非試してみてください。
• 本記事も、以下のコースで学んだ内容をもとに作成しております。

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