[알고리즘] 버블 정렬 (Bubble Sort)

버블 정렬이란

1번째와 2번째 값을 비교, 2번째와 3번째 값을 비교, ... , n-1번째와 n번째 값을 비교하여 자료를 정렬하는 방식, 제일 큰 값을 맨 뒤로 보내며 정렬한다.

 

n-1번째 값 < n번째 값 이면 그대로 두고

n-1번째 값 > n번째 값 이면 둘의 위치를 변경합니다.  

 

버블정렬

 

버블 정렬 예

예) [4, 6, 2, 9, 1]

 

1단계 : [4, 6, 2, 9, 1]        #4와 6을 비교, 4 < 6 이면 그대로 둡니다.

2단계 : [4, 6, 2, 9, 1]        #6과 2를 비교, 6 > 2 이므로 위치를 변경

              [4, 2, 6, 9, 1]

3단계 : [4, 2, 6, 9, 1]        #6과 9를 비교, 6 < 9 이면 그대로 둡니다.

4단계 : [4, 2, 6, 9, 1]        #9와 1를 비교, 9 > 1 이므로 위치를 변경

              [4, 2, 6, 1, 9]

 

이제 for문 한 번을 순회했습니다.

이 과정에서 가장 큰 숫자인 9가 맨 뒤로 왔습니다.

그러면, 맨 뒷자리를 제외하고 다시 한번 for문을 반복하면 됩니다.

 

5단계 : [4, 2, 6, 1, 9]         #4와 2을 비교, 4 > 2 이므로 위치 변경

              [2, 4, 6, 1, 9]

6단계 : [2, 4, 6, 1, 9]         #4와 6을 비교, 4 < 6 이면 그대로 둡니다.

7단계 : [2, 4, 6, 1, 9]         #6와 1을 비교, 6 > 1 이므로 위치 변경

              [2, 4, 1, 6, 9]

 

이제 두 번째로 큰 숫자인 6이 9 앞으로 왔습니다.

여기까지만 비교하시면 됩니다. 6과 9를 비교할 필요는 없습니다.

 

8단계 : [2, 4, 1, 6, 9]         #2와 4을 비교 -> 2 < 4 이면 그대로 둡니다.

9단계 : [2, 4, 1, 6, 9]         #4와 1을 비교 -> 4 > 1 이므로 위치 변경

              [2, 1, 4, 6, 9]

 

이제 세 번째로 큰 숫자인 4가 6 앞으로 왔습니다.

마지막 비교만 하면 됩니다.

 

10단계 : [2, 1, 4, 6, 9]        #2와 1을 비교 -> 2 > 1 이므로 위치 변경

                [1, 2, 4, 6, 9]

 

자, 모두 정렬이 되었습니다.

 

파이썬에서 두 변수의 값을 swap 하는 방법

다른 언어에서는 두 변수의 값을 swap 할 때 임시 변수를 하나 생성해야 하지만

파이썬의 경우 쉽게 swap 할 수 있습니다.

 

a = 3
b = 4
a, b = b, a
print(a) # 4
print(b) # 3

 

버블 정렬 python 코드

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


def bubble_sort(array):
    N = len(array)
    for i in range(N):
        for j in range(N-i-1):
            if array[j] < array[j+1]:
                continue
            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]))

 

버블 정렬의 시간 복잡도

2중 for문을 사용했고 array의 길이만큼 반복한다면 O(N^2) 만큼 걸립니다.

 

버블 정렬