Bubble Sort (버블 정렬)

버블 정렬

두 개의 데이터를 서로 비교 하면서 큰지, 작은지의 여부에 따라 정렬하는 방법

시간복잡도는 O(n^2) 으로 가장 단순하면서 오래걸리는 정렬 방법이다.

 

- 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
- 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

 

source : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

파이썬 코드

def bubble(lst):
    for j in range(len(lst)):
        for i in range(len(lst)-1):
            if lst[i] > lst[i+1]:
                lst[i],lst[i+1] = lst[i+1], lst[i]
            else :
                pass
    return lst