[Algorithm] Bubble Sort (거품 정렬)

0. Bubble Sort (거품 정렬) 이란?

거품 정렬은 가장 간단한 정렬 방법 중 하나로, 첫 번째 값과 두 번째 값을 비교하고 더 큰 것을 뒤로 보내고, 두 번째 값 (앞에서 바뀌었다면 원래는 첫 번째 값일것이다)과 세 번째 값을 비교하고, 이 과정을 정렬될 때까지 반복하여 모든 원소를 비교하는 방법이다. 

 

이 과정을 거치면 첫 번째 정렬에서 최댓값이 맨 뒤로 갈 것이다. 가장 큰 값은 누구와 비교해도 뒤로 밀리기 때문이다. 따라서 원소의 갯수가 N개라면, 두 번째 과정에서는 첫 번째부터 n-1번째까지만 정렬하면 된다. 이 과정을 원소가 하나 남을때까지만 반복하므로 이중 포문으로 구현할 수 있다. 따라서 O(n^2)의 시간복잡도를 가지게 된다.

 

1. 구현

원소가 1과 100 사이의 자연수라고 할 때, 다음과 같이 구현할 수 있다.

n = int(input())
nums = input()
num = nums.split()
max = 0
max_idx = 0

for i in range(n):
    num[i] = (int)(num[i])

sorted = False

while not sorted:
    sorted = True
    for i in range(n-1):
        if num[i] > num[i+1]:
            num[i], num[i+1] = num[i+1], num[i]
            sorted = False

for i in range(n):
    print(num[i], end=' ')

 

처음 값이 최댓값이 되어야 하므로 max를 범위 밖의 작은 값 0으로 설정한다.

sorted를 매번 배열을 돌 때마다 True로 초기화하고, 만약 값이 한 번이라도 바뀌면 False로 한다. 이는 정렬되지 않았음을 뜻하므로, 다시 정렬 과정을 거칠 수 있도록 while문의 조건을 걸어준다. 매 while문마다 배열을 한 번씩 돌며 더 큰 값을 뒤로 보내주는 작업을 반복한다.