거품이 올라오는 것처럼 정렬하는 bubble sort(버블 정렬)

1. 개요

 

인접한 두개의 원소를 비교하면서 자리를 계속 교환하면서 정렬하는 알고리즘

 

첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동

 

한 단계가 끝나면, 가장 큰 원소가 마지막 자리로 이동함

 

교환하면서 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 부름

 

 

2. 예시를 통해 이해하는 버블 정렬

 

55, 7, 78, 12, 42를 정렬한다고 생각해보자.

 

 

먼저 55와 7을 비교하여, 55가 더 크니까 자리를 바꾼다.

 

 

다음 55와 78을 비교하여, 78이 더 크니까 자리를 바꾸지 않는다.

 

다음 78과 12를 비교하여 78이 더 크니까 자리를 바꾼다

 

 

마지막으로 78과 42를 비교하여, 78이 더 크니까 자리를 바꾼다.

 

그러면 배열에서 가장 큰 원소인 78이 마지막 자리로 오면서 78은 정렬이 끝났다

 

 

 

그러면 정렬된 78을 제외한 나머지 7,55,12,42에 대해 똑같은 과정을 반복한다.

 

처음 7과 55를 비교하여 55가 더 크니까 자리를 바꾸지 않고,

 

55와 12를 비교하여 55가 더 크니까 자리를 바꾸고

 

55와 42를 비교하여, 55가 더 크니까 자리를 바꾸고.

 

그러면 가장 큰 55가 마지막에 오면서 55도 정렬이 끝났다

 

 

다음 7,12,42를 똑같은 과정을 반복한다.

 

7과 12를 비교하여 12가 더 크니 자리를 바꾸지 않고, 12와 42를 비교하여 42가 더 크니 자리를 바꾸지 않는다.

 

그러면 42가 마지막에 오면서, 42,55,78이 정렬이 끝났다

 

다음으로 7과 12를 비교하면서 12가 더 크니 자리를 바꾸지 않는다.

 

12가 마지막에 오면서 12,42,55,78이 정렬이 끝났다.

 

마지막 7은 비교할 것이 없으므로 그 자리에 두면 정렬이 끝난다.

 

 

3. 구현 예시

 

비교할 구간이 처음에 0~n-1까지이고, 왼쪽 원소 j번에 대해 오른쪽인 j+1과 비교하여 오른쪽이 더 크면 그대로 두고

 

왼쪽이 더 크면 swap과정을 수행한다.

 

하나의 과정이 끝나면 비교할 구간은 0~n-2로 1칸 줄어든다..

 

그래서 비교할 구간의 끝지점 i를 n-1~1까지 반복하고, 비교 원소 j는 j와 j+1을 선택해야하니까 0부터 i-1까지 반복하면 될 것이다

 

#버블정렬

array = [7,5,9,0,3,1,6,2,4,8]

n = len(array) #배열의 길이

for i in range(n-1,0,-1): ##비교 구간의 끝지점 선택
    
    for j in range(0,i): ##비교 원소 선택
        
        if array[j] > array[j+1]: ##왼쪽 원소가 더 크다면..
            
            array[j],array[j+1] = array[j+1],array[j] ##두 원소의 자리를 바꾼다

print(array)

 

 

4. 시간복잡도

 

직관적으로 n번 반복하는 반복문을 2중으로 사용하므로 $O(n^{2})$임을 알 수 있다

 

그러니까 당연히 데이터의 수가 매우 많으면 비효율적이다

 

하지만 소스코드 안에 존재하는 기본적인 테크닉을 이해할 필요가 있겠다

 

"비교구간을 줄여나가면서, 서로 다른 두 원소를 선택하여 자리를 바꾸는 일"

 

 

5. 연습문제

 

2750번: 수 정렬하기 (acmicpc.net)

2750번: 수 정렬하기

 

$O(n^{2})$의 정렬 알고리즘으로 해결할 수 있는 문제

 

선택정렬에 비해 버블정렬이 더 느리게 나온다

 

from sys import stdin

n = int(stdin.readline())

array = []

for _ in range(n):
    
    i = int(stdin.readline())

    array.append(i)

for i in range(n-1,0,-1):
    
    for j in range(0,i):
        
        if array[j] > array[j+1]:
            
            array[j],array[j+1] = array[j+1],array[j]

for num in array:
    
    print(num)