schedule2019-05-13

バブルソートのコード | Python

Python3でバブルソートをするコードです。

バブルソート

バブルソートは隣り合う要素を比較しながら整列させていくソート方法。

手順は以下の3ステップです。

  1. 後ろから順に隣り合う要素を比較する。
  2. 左が右の要素に比べ大きい場合交換。
  3. 走査範囲を前からひとつ狭める。

3.は走査範囲の中で一番小さい値が先頭に来て比較が不要になるため、範囲を狭めています。 2.の交換を小さい場合にすると、降順になります。

ソートのアニメーション

babble-sort

アニメーションは以下の記事で作成しました。

コード

内側のループ回数が1回ずつ減る、2重のループです。

平均計算量はO(n2)O(n^2)です。

import random


def babble_sort(arr):
    """ バブルソート """
    length = len(arr)

    for i in range(length):
        # 3. 走査範囲を前からひとつ狭める
        for j in reversed(range(i+1, length)):
            # 1. 後ろから順に隣り合う要素を比較する。
            if arr[j-1] > arr[j]:
                # 2. 左が右の要素に比べ大きい場合交換する。
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr


if __name__ == "__main__":
    # 長さ10のランダムな配列
    arr = list(range(10))
    src = random.sample(arr, len(arr))

    print(src)
    # [7, 2, 5, 3, 1, 6, 9, 4, 8, 0]

    dst = babble_sort(src)
    print(dst)
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

値の交換はa, b = b, aを使って1行で書いています。