バブルソート – TauStation

概要

バブルソートは、すべてのデータを一つずつチェックしながら、（昇順の場合）最も大きいデータを後ろに押し出していく。

たとえば以下のような初期データ列があるとする。

3, 4, 1, 2, 0

最初のループでは、全データの中で最大のものが一番最後に来るようにする。

3, 4, 1, 2, 0
3, 4, 1, 2, 0　→　3, 1, 4, 2, 0
3, 1, 4, 2, 0　→　3, 1, 2, 4, 0
3, 1, 2, 4, 0　→　3, 1, 2, 0, 4

3, 1, 2, 0, 4　→　1, 3, 2, 0, 4
1, 3, 2, 0, 4　→　1, 2, 3, 0, 4
1, 2, 3, 0, 4　→　1, 2, 0, 3, 4

1, 2, 0, 3, 4
1, 2, 0, 3, 4　→　1, 0, 2, 3, 4

1, 0, 2, 3, 4　→　0, 1, 2, 3, 4

ループ回数は $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$

コード

Pythonによるバブルソートのコード例。

def bubble_sort(data):
    for m in reversed(range(0, len(data))):
        for n in range(0, m):
            print(data, end=' -> ')
            if data[n] > data[n+1]:
                data[n], data[n+1] = data[n+1], data[n]
            print(data)
        print()


data = [3, 4, 1, 2, 0]
bubble_sort(data)

# [0, 1, 2, 3, 4]

def bubble_sort(data):

for m in reversed(range(0, len(data))):

for n in range(0, m):

print(data, end=' -> ')

if data[n] > data[n+1]:

data[n], data[n+1] = data[n+1], data[n]

print(data)

print()

data = [3, 4, 1, 2, 0]

bubble_sort(data)

# [0, 1, 2, 3, 4]

安定ソート

バブルソートは安定ソートである。すなわち、同じソートキーのデータについて、ソート後も元の順序が保持される。

def bubble_sort_2d(data):
    for m in reversed(range(0, len(data))):
        for n in range(0, m):
            print(data, end=' -> ')
            if data[n][1] > data[n+1][1]:
                data[n], data[n+1] = data[n+1], data[n]
            print(data)
        print()


data = [
    [1, 50],
    [2, 40],
    [3, 30],
    [4, 30],
    [5, 40]]
bubble_sort_2d(data)

# [[3, 30], [4, 30], [2, 40], [5, 40], [1, 50]]

def bubble_sort_2d(data):

for m in reversed(range(0, len(data))):

for n in range(0, m):

print(data, end=' -> ')

if data[n][1] > data[n+1][1]:

data[n], data[n+1] = data[n+1], data[n]

print(data)

print()

data = [

[1, 50],

[2, 40],

[3, 30],

[4, 30],

[5, 40]]

bubble_sort_2d(data)

# [[3, 30], [4, 30], [2, 40], [5, 40], [1, 50]]

概要

コード

安定ソート

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル