[CLRS] [2-4] Bubble Sort(버블 정렬)

1. Bubble Sort? 

- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
--> 인접한 2개의 노드를 비교하여 크기순으로 서로 교환을 해준다.

 

2. 더 자세히!

- 버블 정렬은 인접된 두 노드, 즉 (첫 번째, 두번째),(두 번째, 세 번째),(세 번째,네 번째)... 이런 식으로
마지막 노드를 비교하여 교환하면서 데이터를 정렬한다.

- 그림을 보면 더 쉽게 이해가능하다.

- 반대로 마지막 부터 시작으로 역순으로 버블이 움직여도 괜찮다.(CLRS에선 역순으로 움직인다.)

 

3. Code(Python)

def bubble_sort(arr,n):
    for i in range(n):
        for j in range(n,i,-1):
            if arr[j] < arr[j-1]:
                arr[j] , arr[j-1] = arr[j-1],arr[j]

 

4. Bubble Sort의 시간복잡도

- 결국 n-1부터 1까지의 합만큼 실행이 된다.

- 즉, n(n-1)/2 

- T(n) = O(n^2)이라고 할 수 있다.