[딩코딩코 2025 코딩테스트 필수 알고리즘] - 8. 버블 정렬

본 글에 사용된 코드와 이미지의 일부는

딩코딩 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 강의를 참조하여 발췌·활용하였습니다.

[본 게시물은 파트너스 활동의 일환으로 소정의 수수료를 받을 수 있습니다.] https://inf.run/tXMrp\

---

버블 정렬

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를 .. 이런 식으로 비교하면서 자료를 정렬하는 방식이다.

작은 숫자, 큰 숫자 비교 시 그대로 두고
큰 숫자, 작은 숫자 비교 시 둘의 위치를 변경하면 된다.

예시를 통해 살펴보자.

[4,6,2,9,1]

1단계 : 4,6 비교 -> 4<6 -> [4,6,2,9,1]
2단계 : 6,2 비교 -> 6>2 -> [4,2,6,9,1]
3단계 : 6,9 비교 -> 6<9 -> [4,2,6,9,1]
4단계 : 9,1 비교 -> 9>1 -> [4,2,6,1,9]

이렇게 한 바퀴를 돌게 되면 가장 큰 숫자인 9가 맨 뒤로 왔다.
그러면, 맨 뒷자리를 제외하고 다시 한 번 돌리면 된다.

5단계 : 4,2 비교 -> 4>2 -> [2,4,6,1,9]
6단계 : 4,6 비교 -> 4<6 -> [2,4,6,1,9]
7단계 : 6,1 비교 -> 6>1 -> [2,4,1,6,9] 

그러면 이제 두 번째로 큰 숫자인 6이 맨 뒤에서 두번째로 오게 된다.
6,9 는 비교할 필요는 없다.

8단계 : 2,4 비교 -> 2<4 -> [2,4,1,6,9]
9단계 : 4,1 비교 -> 4>1 -> [2,1,4,6,9]
10단계 : 2,1 비교 -> 2>1 -> [1,2,4,6,9]

이렇게 10번만에 모두 정렬이 되었다.

버블 정렬 코드로 구현

이제 코드로 구현을 해보자.

위에서 살펴봤던 로직 그대로 코드에 옮기면 된다.
어떤 식으로 반복문을 써야 할까?

1번째 : [4, 6, 2, 9, 1]
         →  →  →  →  → 비교!
2번째 : [4, 2, 6, 1, 9]
         →  →  →  → 비교!
3번째 : [2, 4, 1, 6, 9]
         →  →  → 비교!
4번째 : [2, 1, 4, 6, 9]
         →  → 비교!

for i in range(5 - 1): # 4번만 비교 
    for j in range(5 - i - 1): # 마지막 원소까지 가지 않아도 됨
        print(j)

배열의 크기만큼 반복했다가, 1개씩 줄어들면서 반복하는 반복문을 구현하면 된다.

input = [4, 6, 2, 9, 1]

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

bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))

버블 정렬 시간 복잡도

이 함수의 시간 복잡도는 어떻게 될까?

첫번째 for 문, 두번째 for문 각각 O(N) 이기 때문에 O(N^2) 만큼 시간복잡도가 걸린다.