버블정렬 (Bubble Sort)

📌 버블정렬 (Bubble Sort)

버블 정렬은 뒤에서부터 앞으로 정렬하는 특징을 갖고 있다. 

가장 큰 수가 맨 뒤로 가고 그 다음 큰 수가 그 앞에 위치하게 된다.

시간복잡도는 O(n^2)이다.

 

👉 과정

[3, 2, 4, 5, 1] 
3과 2 swap

가장 앞에 수와 그 다음 수를 비교해서 앞에 있는 수가 더 크면 두 수를 swap한다.

 

[2, 3, 4, 5, 1] 

3과 4를 비교하는데 3이 더 작기 때문에 swap 없이 넘어간다.

 

[2, 3, 4, 5, 1] 

4와 5도 마찬가지로 4가 5보다 더 작기 때문에 swap 없이 넘어간다.

 

[2, 3, 4, 5, 1] 
5와 1 swap

5가 1보다 크기 때문에 5와 1을 swap

 

[2, 3, 4, 1, 5] 

가장 큰 수인 5는 자리가 정해졌기 때문에 이 다음부터는 5 바로 전까지만 위에 과정을 반복해 비교한다.

 

[2, 3, 4, 1, 5]
4와 1 swap

[2, 3, 1, 4, 5]
3과 1 swap

[2, 1, 3, 4, 5]
2와 1 swap

[1, 2, 3, 4, 5]
정렬 끝

 

👉 구현

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr