バブルソート

バブルソートは、単純なソートアルゴリズムであり、隣接する値を比較し、条件に基づいて要素を交換します.

昇順の並べ替えでは、何をするかをベースにソートし、2つの値をcomapresし、位置を変更し、値を通してそれを反復し、最後に最高値を配置します.

この例では、この値を
value list -> [ 6 , 5 , 3 , 1 , 8 , 7 ]

追跡

ステージ1

Input
[6, 5, 3, 1, 8, 7]

compare position 0 and 1 values
---> 6>5 position 0 is greate than 1, swap it
[5, 6, 3, 1, 8, 7]

compare position 1 and 2 values
---> 6>3 position 1 is greate than 2, swap it
[5, 3, 6, 1, 8, 7]

compare position 2 and 3 values
--------> 6>1 position 2 is greate than 3, swap it
[5, 3, 1, 6, 8, 7]

compare position 3 and 4 values
--------> 6>8 position 3 is less than 4, no swap
[5, 3, 1, 6, 8, 7]

compare position 4 and 5 values
--------> 8>7 position 4 is greate than 5, swap it
[5, 3, 1, 6, 7, 8]

最後の位置
ステージ2

Input
[5, 3, 1, 6, 7]

compare position 0 and 1 values
--------> 5>3 position 0 is greate than 1, swap it
[3, 5, 1, 6, 7]

compare position 1 and 2 values
--------> 5>1 position 1 is greate than 2, swap it
[3, 1, 5, 6, 7]

compare position 2 and 3 values
--------> 5>6 position 2 is less than 3, no swap
[3, 1, 5, 6, 7]

compare position 3 and 4 values
--------> 6>7 position 3 is less than 4, no swap
[3, 1, 5, 6, 7]

最後の位置
ステージ3

Input
[3, 1, 5, 6]

compare position 0 and 1 values
--------> 3>5 position 0 is less than 1, no swap
[3, 5, 1, 6]

compare position 1 and 2 values
--------> 5>1 position 1 is greate than 2, swap it
[3, 1, 5, 6]

compare position 2 and 3 values
--------> 5>6 position 2 is less than 3, no swap
[3, 1, 5, 6]

最後の位置
ステージ4

Input
[3, 1, 5]

compare position 0 and 1 values
--------> 3>1 position 0 is greate than 1, swap it
[1, 3, 5]

compare position 1 and 2 values
--------> 3>1 position 1 is less than 2, no swap
[1, 3, 5]

最後の位置
ステージ5

Input
[1, 3]

compare position 0 and 1 values
--------> 3>1 position 0 is less than 1, no swap
[1, 3]

最後の位置の値
結果1、3、5、6、7、8

def bubbleSort(k):
    last = 0
    for i in range(0,len(k)):
        # reduce the last value to avoid over lapping
        for j in range(0,len(k)-1-last):
            # compare the adjustent value
            if k[j] > k[j+1]:
                k[j], k[j+1] = k[j+1], k[j]

        last+=1
        print(k)
    return k

k = [3,40,2,0,10]
bubbleSort(k)

"""
result
[3, 2, 0, 10, 40]
[2, 0, 3, 10, 40]
[0, 2, 3, 10, 40]
[0, 2, 3, 10, 40]
[0, 2, 3, 10, 40]

[0, 2, 3, 10, 40]
"""

アナザーメソッド

値が既にソートされている場合、またはプロセスの途中でそれがソートされる場合は、最後までプロセスを行う必要はありません.値がソートされたときに停止できます.

def bubbleSort(k):
    last = 0
    for i in range(0,len(k)):
        # when the list is already sorted, its better to stop this will increase the process time
        done = True
        # reduce the last value to avoid over lapping
        for j in range(0,len(k)-1-last):
            # compare the adjustent value
            if k[j] > k[j+1]:
                k[j], k[j+1] = k[j+1], k[j]
                done = False
        if done:
            break
        last+=1
        print(k)
    return k

k = [3,40,2,0,10]
bubbleSort(k)

"""
result
[3, 2, 0, 10, 40]
[2, 0, 3, 10, 40]
[0, 2, 3, 10, 40]

[0, 2, 3, 10, 40]
"""

結果が最初まで実行された結果の違いを見ることができます.リストがソートされると、2番目のメソッドでは停止します.

時間複雑

バブルソートは、最悪の場合と値(n 2)の平均複雑さ、O(n)の場合は、値が既にソートされた最良のケースがあります.