【アルゴリズム】Pythonで記述するバブルソート

アルゴリズムサムネイル アルゴリズム

16

この記事を執筆いたしました16(ヒロ)と言うものです。現役のエンジニアで初学者向けにPythonを教えていたり、RPAでの業務効率化を行ったりサーバー構築なんかをしています。

       
  • 職業:

    エンジニア

  • 主な業務内容:

    初学者向けPython教育、RPA、サーバー構築

  • 所有資格:

    基本情報技術者、Python3エンジニア認定基礎試験

今回はソートアルゴリズムの中のバブルソートについて解説していきます。

バブルソートとは

すべてのとなりあった値を比べていって、小さい方の値が前に移動するように交換していく方法です。以下のような特徴があります。

特徴

データを昇順(小さい順)に並び替える

プログラムが単純で実装しやすい

大量のデータの並び替えには時間がかかる

バブルソートのイメージ

バブルソートとは基本的なアルゴリズムのひとつです。

すべての隣り合った値を比べていき、小さい値を先頭に移動させながら交換していく方法です。

バブルソートイメージ1

整列されていない状態の配列があったとします。

この整列されていない配列をバブルソートを使って小さい順に並び替えを行うには、まず末尾の2つの値(青背景の値)を比べます。

2つの値を比べて後ろの方が小さい値であれば、前方に移動させる必要があるので交換します。

バブルソートイメージ2

入れ替えをした状態のイメージが上の画像になります。

この比較を先頭に向かって順番に繰り返していきます。なので次は下の画像の位置の比較を行っていきます。

バブルソートイメージ3

2つの値を比べた時に後ろの値が小さいので入れ替えを行います。

バブルソートイメージ4
16
16

さらに同じように先頭まで繰り返していきます!

バブルソートイメージ5

2つの値を比較します。後ろの値の方が小さいので入れ替えを行います。

バブルソートイメージ6

上の画像が入れ替え後です。

バブルソートイメージ7

2つの値を比較します。後ろの値の方が小さいので入れ替えを行います。

バブルソートイメージ8

上の画像が入れ替え後です。

バブルソートイメージ9

2つの値を比較します。後ろの値の方が小さいので入れ替えを行います。

バブルソートイメージ10

先頭まで繰り返しを行い先頭の値が決まりました。

まだ先頭以外の部分が整列していない状態なので末尾から同じように繰り返し比較をおこなっていきます。

バブルソートをフローチャートで表現

バブルソート_フローチャート

①バブルソートで並び替える範囲の開始位置を先頭から後ろに移動していきながら繰り返しを行う。

②末尾の2つを比較をしながら先頭に移動しながら繰り返しを行う。

③2つの値を比較する。

④後ろの値が小さければ入れ替えを行う。

バブルソートをPythonで表現

Pythonでバブルソートを実装

bubble_sort_num = [2, 5, 6, 3, 4, 1]

for i in range(len(bubble_sort_num)-1):
    for j in range(len(bubble_sort_num)-1, i, -1):
        if(bubble_sort_num[j] < bubble_sort_num[j-1]):
            tmp = bubble_sort_num[j]
            bubble_sort_num[j] = bubble_sort_num[j-1]
            bubble_sort_num[j-1] = tmp

print(bubble_sort_num)

# 結果
# [1, 2, 3, 4, 5, 6]

まとめ

アルゴリズムのバブルソートについてフローチャート、Pythonコードを用いて解説してきました。実際にプログラムを動かしてみるとわかりやすと思います。環境構築不要でなおかつ無料でPythonを実行できるGoogleのサービス「Google Colaboratory」があるのでよかったら利用してみてください。使い方などは下記の記事にまとめてますのでご覧ください。

コメント

タイトルとURLをコピーしました