버블 정렬(Bubble Sort)

개요

버블정렬(Bubble Sort)은 선택 정렬(Select Sort)과 유사한 알고리즘이다.
서로 인접한 두 원소를 비교하여 조건에 맞거나, 맞지 않을 경우 자리를 교환하며 정렬하는 알고리즘이다.

이름의 유래로는 정렬 과정에서 원소의 이동이 거품과 비슷한 모습을 보인다고 해서 지어졌다고 한다.

처리 과정

데이터: [4, 6, 2, 7, 8, 5, 0, 1]

1회전

1. 4와 6을 비교, 6이 더 큼으로 교환하지 않음
2. 6과 2를 비교, 2가 더 작음으로 교환
   => [4, 2, 6, 7, 8, 5, 0, 1]
3. 6과 7을 비교, 7이 더 큼으로 교환하지 않음
4. 7과 8을 비교, 8이 더 큼으로 교환하지 않음
5. 8과 5를 비교, 5가 더 작음으로 교환
   => [4, 2, 6, 7, 5, 8, 0, 1]
6. 8과 0을 비교, 0이 더 작음으로 교환
   => [4, 2, 6, 7, 5, 0, 8, 1]
7. 8과 1를 비교, 1이 더 작음으로 교환
   => [4, 2, 6, 7, 5, 0, 1, 8]

1회전 결과

[4, 2, 6, 7, 5, 0, 1, 8]

2회전

1. 2와 4를 비교, 2가 더 작음으로 교환
   => [2, 4, 6, 7, 5, 0, 1, 8]
2. 4와 6을 비교, 6이 더 큼으로 교환하지 않음
3. 6과 7을 비교, 7이 더 큼으로 교환하지 않음
4. 7과 5를 비교, 5가 더 작음으로 교환
   => [2, 4, 6, 5, 7, 0, 1, 8]
5. 7과 0을 비교, 0이 더 작음으로 교환
   => [2, 4, 6, 5, 0, 7, 1, 8]
6. 7과 1를 비교, 1이 더 작음으로 교환
   => [2, 4, 6, 5, 0, 1, 7, 8]

2회전 결과

[2, 4, 6, 5, 0, 1, 7, 8]

3회전

1. 2와 4를 비교, 4가 더 큼으로 교환하지 않음
2. 4화 6을 비교, 6이 더 큼으로 교환하지 않음
3. 6과 5를 비쿄, 5가 더 작음으로 교환
   => [2, 4, 5, 6, 0, 1, 7, 8]
4. 6과 0을 비교, 0이 더 작음으로 교환
   => [2, 4, 5, 0, 6, 1, 7, 8]
5. 6과 1를 비교, 1이 더 작음으로 교환
   => [2, 4, 5, 0, 1, 6, 7, 8]

3회전 결과

[2, 4, 5, 0, 1, 6, 7, 8]

4회전

1. 2와 4를 비교, 4가 더 큼으로 교환하지 않음
2. 4와 5를 비교, 5가 더 큼으로 교환하지 않음
3. 5와 0을 비교, 0이 더 작음으로 교환
   => [2, 4, 0, 5, 1, 6, 7, 8]
4. 5와 1를 비교, 1이 더 작음으로 교환
   => [2, 4, 0, 1, 5, 6, 7, 8]

4회전 결과

[2, 4, 0, 1, 5, 6, 7, 8]

5회전

1. 2와 4를 비교, 4가 더 큼으로 교환하지 않음
2. 4와 0을 비교, 0이 더 작음으로 교환
   => [2, 0, 4, 1, 5, 6, 7, 8]
3. 4와 1를 비교, 1이 더 작음으로 교환
   => [2, 0, 1, 4, 5, 6, 7, 8]

5회전 결과

[2, 0, 4, 1, 5, 6, 7, 8]

6회전

1. 2와 0을 비교, 0이 더 작음으로 교환
   => [0, 2, 1, 4, 5, 6, 7, 8]
2. 2와 1을 비교, 1이 더 작음으로 교환
   => [0, 1, 2, 4, 5, 6, 7, 8]

6회전 결과

[0, 1, 2, 4, 5, 6, 7, 8]

버블 정렬 결과

[4, 6, 2, 7, 8, 5, 0, 1] ==> [0, 1, 2, 4, 5, 6, 7, 8]

코드(python)

주석 미포함

datas = [4, 6, 2, 7, 8, 5, 0, 1]

for i in range(len(datas)):
    for j in range(1, len(datas)-i):
        if datas[j-1] > datas[j]:
            datas[j-1], datas[j] = datas[j], datas[j-1]

print(f"결과: {datas}")

주석 포함

datas = [4, 6, 2, 7, 8, 5, 0, 1]

# 0번 부터 시작함
for i in range(len(datas)):
    # (0,1), (1,2), (2,3)... 이런식으로 비교함
    # 다음에 비교 다하면 i + 1되면서
    # (1,2), (2,3), (3,4)... 비교함
    for j in range(1, len(datas)-i):
        # 조건을 만족(이전 위치가 현재 위치보다 크면)하면 위치 변경
        if datas[j-1] > datas[j]:
            print(f"{datas[j-1]} 이(가) {datas[j]} 보다 큼으로 변경")
            print(datas, '=>', end=' ')
            datas[j-1], datas[j] = datas[j], datas[j-1]
            print(datas)
            print()

    print(f"{i+1}회전: {datas}")
    print()

# 결과
print(f"결과: {datas}")

print 내용

6 이(가) 2 보다 큼으로 변경
[4, 6, 2, 7, 8, 5, 0, 1] => [4, 2, 6, 7, 8, 5, 0, 1]

8 이(가) 5 보다 큼으로 변경
[4, 2, 6, 7, 8, 5, 0, 1] => [4, 2, 6, 7, 5, 8, 0, 1]

8 이(가) 0 보다 큼으로 변경
[4, 2, 6, 7, 5, 8, 0, 1] => [4, 2, 6, 7, 5, 0, 8, 1]

8 이(가) 1 보다 큼으로 변경
[4, 2, 6, 7, 5, 0, 8, 1] => [4, 2, 6, 7, 5, 0, 1, 8]

1회전: [4, 2, 6, 7, 5, 0, 1, 8]

4 이(가) 2 보다 큼으로 변경
[4, 2, 6, 7, 5, 0, 1, 8] => [2, 4, 6, 7, 5, 0, 1, 8]

7 이(가) 5 보다 큼으로 변경
[2, 4, 6, 7, 5, 0, 1, 8] => [2, 4, 6, 5, 7, 0, 1, 8]

7 이(가) 0 보다 큼으로 변경
[2, 4, 6, 5, 7, 0, 1, 8] => [2, 4, 6, 5, 0, 7, 1, 8]

7 이(가) 1 보다 큼으로 변경
[2, 4, 6, 5, 0, 7, 1, 8] => [2, 4, 6, 5, 0, 1, 7, 8]

2회전: [2, 4, 6, 5, 0, 1, 7, 8]

6 이(가) 5 보다 큼으로 변경
[2, 4, 6, 5, 0, 1, 7, 8] => [2, 4, 5, 6, 0, 1, 7, 8]

6 이(가) 0 보다 큼으로 변경
[2, 4, 5, 6, 0, 1, 7, 8] => [2, 4, 5, 0, 6, 1, 7, 8]

6 이(가) 1 보다 큼으로 변경
[2, 4, 5, 0, 6, 1, 7, 8] => [2, 4, 5, 0, 1, 6, 7, 8]

3회전: [2, 4, 5, 0, 1, 6, 7, 8]

5 이(가) 0 보다 큼으로 변경
[2, 4, 5, 0, 1, 6, 7, 8] => [2, 4, 0, 5, 1, 6, 7, 8]

5 이(가) 1 보다 큼으로 변경
[2, 4, 0, 5, 1, 6, 7, 8] => [2, 4, 0, 1, 5, 6, 7, 8]

4회전: [2, 4, 0, 1, 5, 6, 7, 8]

4 이(가) 0 보다 큼으로 변경
[2, 4, 0, 1, 5, 6, 7, 8] => [2, 0, 4, 1, 5, 6, 7, 8]

4 이(가) 1 보다 큼으로 변경
[2, 0, 4, 1, 5, 6, 7, 8] => [2, 0, 1, 4, 5, 6, 7, 8]

5회전: [2, 0, 1, 4, 5, 6, 7, 8]

2 이(가) 0 보다 큼으로 변경
[2, 0, 1, 4, 5, 6, 7, 8] => [0, 2, 1, 4, 5, 6, 7, 8]

2 이(가) 1 보다 큼으로 변경
[0, 2, 1, 4, 5, 6, 7, 8] => [0, 1, 2, 4, 5, 6, 7, 8]

6회전: [0, 1, 2, 4, 5, 6, 7, 8]

7회전: [0, 1, 2, 4, 5, 6, 7, 8]

8회전: [0, 1, 2, 4, 5, 6, 7, 8]

결과: [0, 1, 2, 4, 5, 6, 7, 8]

시간 복잡도

시간 복잡도는 (n-1) + (n-2) + (n-3) + ... + 2 + 1 ==> n (n-1) / 2 이므로 O(n^2)이다.

또한 버블 정렬은 정렬을 했던 안했던 비교 작업을 수행하기 때문에 최선, 평균, 최악 모두 같은 O(n^2)의 시간이 걸린다.

공간 복잡도

주어진 배열 안에서 교환이 이루어지므로 O(n)이다.

장점

1. 간단하게 만들 수 있다.
2. 특히 파이썬은 a, b = b, a를 통해 교환이 가능해 temp와 같은 다른 변수를 선언할 필요가 없다.
3. 안정 정렬(stable sort)다.

단점

1. 시간복잡도가 모두 O(n^2)이여서 비효율적이다.
2. 정렬이 안되어있을 수록 교환이 많이 일어난다.

ref

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html