[알고리즘] 파이썬으로 거품정렬 구현하기 :: bubble sort in python

파이썬으로 bubble sort 구현하기

1. bubble sort란?

거품 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간복잡도는 \(O(n^2)\) 으로 상당히 느리지만 구현이 쉽다는 장점이 있다.

2. bubble sort in python

이를 python3에서 구현하면 다음과 같다.

# bubble sort
def bubble(v) :
    l = len(v)
    for i in range(l-1):
        for j in range(l-i-1) :
            if  v[j]>v[j+1] :
                v[j+1], v[j] = v[j], v[j+1]
    return v

* bubble sort 예시

> bubble([5,4,3,2,1])

[1, 2, 3, 4, 5]

i = 0

j = 0 : 4 5 3 2 1

j = 1 : 4 3 5 2 1

j = 2 : 4 3 2 5 1

j = 3 : 4 3 2 1 5

i = 1

j = 0 : 3 4 2 1 5

j = 1 : 3 2 4 1 5

j = 2 : 3 2 1 4 5

i = 2

j = 0 : 2 3 1 4 5

j = 1 : 2 1 3 4 5

i = 3

j = 0 : 1 2 3 4 5