파이썬의 버블소트

버블 정렬은 가장 간단한 정렬 알고리즘으로 인접한 값을 비교하고 조건에 따라 요소를 교환합니다.

오름차순 정렬에서 기본적으로 수행하는 작업은 두 값을 비교하고 위치를 변경하고 값을 반복하고 끝에 가장 높은 값을 배치하는 것입니다.



이 예에서는 이 값을 입력으로 사용합니다.
값 목록 --> [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]

마지막 위치 값 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]

마지막 위치 값 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]

마지막 위치 값 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가 잠김

5단계

Input
[1, 3]

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

마지막 위치 값 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]
"""

결과 첫 번째 방법은 끝까지 실행되고 두 번째 방법은 목록이 정렬되면 중지되는 결과의 차이를 볼 수 있습니다.

시간 복잡도

버블 정렬의 평균 복잡성은 최악의 경우 О(n2)이고, 값이 이미 정렬된 경우 최상의 경우 O(n)입니다.