[알고리즘] 버블 정렬 (bubble sort)

 

 

버블정렬(bubble sort) 란?

• 서로 이웃한 두 원소의 크기를 비교한 결과 순서대로 정렬되어 있지 않으면 교환을 반복하여 정렬을 진행하는 알고리즘이다.
• 구체적으로 말하자면 첫 번째 데이터와 두 번째 자료를, 두 번째 자료와 세 번째 자료를 ···· 이런 식으로 마지막 자료까지 서로 크기를 비교하여 교환하며 정렬하는 방식이다. 이렇게 첫번째 회전이 수행이 되고나면 가장 큰 자료가 맨 뒤로 가게 되며 두번째 회전부터는 맨마지막의 자료를 정렬에서 제외하고 이 과정을 반복한다. 
• 가장 간단하지만 비효율적인 알고리즘이다. 이는 위의 예시와 같이 목록이 이미 정렬이 되어있어도 모든 항목을 검사하기 때문에 많은 시간복잡도가 걸리기 때문이다.

코드는 아래와 같다.

def bubble_sort(li):
    n = len(li) #받는 배열의 크기를 n에 담고
    for i in range(n): #배열의 크기만큼 반복한다.
        for j in range(0, n-i-1): # 배열의 총 크기에서 i의 값과 마지막의 1을 뺀 값을 반복한다.
            if li[j] > li[j+1]: 
                li[j], li[j+1] = li[j+1], li[j]